题解：P5307 [COCI 2018/2019 #6] Mobitel

七夕节到了没人一起过，只能录一个不错的 trick 了。

显然有一个三维的

dp_{i,j,k}

表示当前在

(i,j)

路径乘积为

k

的方案数。考虑优化其状态，类似数论分块地，我们将第三维变成至少乘上

k

才能大于等于

n

的方案数，这样的

k

是

O(\sqrt{n})

级别的。

直接 dp 即可，时间复杂度

O(rs\sqrt{n})

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
bool mbs;
const int mod=1e9+7;
const int maxn=320;
const int maxm=3e3+20;
const int maxk=1e6+20;
#define ll long long
int n,m,a[maxn][maxn],k,dp[2][maxn][maxm],rec[maxm],idx,id[maxk];
#define qx(x,y) id[((x)/(y)+((x)%(y)!=0))]
bool mbt;
int main(){
//	cerr<<(&mbs-&mbt)/1024.0/1024.0<<endl;
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read();
	for(int i=1;i<=k;i++) rec[++idx]=(k/i+(k%i!=0));
	sort(rec+1,rec+1+idx);
	idx=unique(rec+1,rec+1+idx)-rec-1;
	for(int i=1;i<=idx;i++) id[rec[i]]=i;
	for(int i=1;i<=n;i++){
		int cur=(i&1);
		for(int j=1;j<=m;j++){
			for(int c=1;c<=idx;c++) dp[cur][j][c]=0;
			if(i==1&&j==1){dp[cur][j][qx(k,a[i][j])]=1;continue;}
			if(i!=1)
				for(int c=1;c<=idx;c++) dp[cur][j][qx(rec[c],a[i][j])]=(dp[cur][j][qx(rec[c],a[i][j])]+dp[cur^1][j][c])%mod;
			if(j!=1)
				for(int c=1;c<=idx;c++) dp[cur][j][qx(rec[c],a[i][j])]=(dp[cur][j][qx(rec[c],a[i][j])]+dp[cur][j-1][c])%mod;
		}
	}
	printf("%d\n",dp[n&1][m][1]);
	return 0;
}

题解：P5307 [COCI 2018/2019 #6] Mobitel

文章操作

相关推荐

评论

题解：P5307 [COCI 2018/2019 #6] Mobitel