本文共 1664 字,大约阅读时间需要 5 分钟。
n ∗ m n*m n∗m的矩阵,求有多少条路径的乘积不小于 S S S。
我们用总路径数减去乘积小于 S S S的路径数
我们很容易想到用 f i , j , k f_{i,j,k} fi,j,k表示到 ( i , j ) (i,j) (i,j)这个点,然后乘积之和为 k k k的 d p dp dp。但是时间复杂度 O ( n m S ) O(nmS) O(nmS)显然难以胜任本题。
我们考虑将 S − 1 S-1 S−1整除分块,用 f i , j , k f_{i,j,k} fi,j,k表示 ( i , j ) (i,j) (i,j)这个点时,再乘上一个大于等于 k k k的数就会大于等于 S S S。
然后我们可以得到动态转移方程
f i , j , k = f i − 1 , j , z + f i , j − 1 , z ( z = S − 1 ⌊ S − 1 k ⌋ ∗ a i , j ) f_{i,j,k}=f_{i-1,j,z}+f_{i,j-1,z}(z=\frac{S-1}{\lfloor\frac{S-1}{k}\rfloor*a_{i,j}}) fi,j,k=fi−1,j,z+fi,j−1,z(z=⌊kS−1⌋∗ai,jS−1)然后 k k k只有 2 ∗ S 2*\sqrt S 2∗S,所以时间复杂度 O ( n m S ) O(nm\sqrt S) O(nmS)
#include#include #include #include using namespace std;const int XJQ=1e9+7,N=310;int n,m,s,t,a[N][N],f[2][N][5000],ans,num[5000],v[1100000],c[N][N],cnt;int main(){ freopen("mobitel.in","r",stdin); freopen("mobitel.out","w",stdout); scanf("%d%d%d",&n,&m,&s); c[1][0]=1;s--; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) c[i][j]=(c[i][j-1]+c[i-1][j])%XJQ; for(int i=1,k;i<=s;i=k+1){ k=s/(s/i); num[++cnt]=s/i; v[num[cnt]]=cnt; } /*for(int i=s;i>=1;i--) v[i]=v[i]?v[i]:v[i+1];*/ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); f[1][1][v[s/a[1][1]]]=1; for(int i=1;i<=n;i++){ memset(f[~i&1],0,sizeof(f[~i&1])); for(int j=1;j<=m;j++) for(int k=1;k<=cnt;k++){ int z=num[k]; if(!f[i&1][j][k]) continue; if(i 0) (f[~i&1][j][v[z/a[i+1][j]]]+=f[i&1][j][k])%=XJQ; if(j 0) (f[i&1][j+1][v[z/a[i][j+1]]]+=f[i&1][j][k])%=XJQ; } } for(int k=1;k<=cnt;k++) (ans+=f[n&1][m][k])%=XJQ; printf("%d",(c[n][m]-ans+XJQ)%XJQ);}
转载地址:http://sukaf.baihongyu.com/