静态网站制作视频,wordpress 分类 文章,青海移动网站建设,网站做下要多少正题 题目大意 n∗mn*mn∗m的矩阵#xff0c;求有多少条路径的乘积不小于SSS。 解题思路
我们用总路径数减去乘积小于SSS的路径数
我们很容易想到用fi,j,kf_{i,j,k}fi,j,k表示到(i,j)(i,j)(i,j)这个点#xff0c;然后乘积之和为kkk的dpdpdp。但是时间复杂度O(nmS)O(nmS)O…正题 题目大意
n∗mn*mn∗m的矩阵求有多少条路径的乘积不小于SSS。 解题思路
我们用总路径数减去乘积小于SSS的路径数
我们很容易想到用fi,j,kf_{i,j,k}fi,j,k表示到(i,j)(i,j)(i,j)这个点然后乘积之和为kkk的dpdpdp。但是时间复杂度O(nmS)O(nmS)O(nmS)显然难以胜任本题。
我们考虑将S−1S-1S−1整除分块用fi,j,kf_{i,j,k}fi,j,k表示(i,j)(i,j)(i,j)这个点时再乘上一个大于等于kkk的数就会大于等于SSS。
然后我们可以得到动态转移方程 fi,j,kfi−1,j,zfi,j−1,z(zS−1⌊S−1k⌋∗ai,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,kfi−1,j,zfi,j−1,z(z⌊kS−1⌋∗ai,jS−1)
然后kkk只有2∗S2*\sqrt S2∗S所以时间复杂度O(nmS)O(nm\sqrt S)O(nmS) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int XJQ1e97,N310;
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 i1;in;i)for(int j1;jm;j)c[i][j](c[i][j-1]c[i-1][j])%XJQ;for(int i1,k;is;ik1){ks/(s/i);num[cnt]s/i;v[num[cnt]]cnt;}/*for(int is;i1;i--)v[i]v[i]?v[i]:v[i1];*/for(int i1;in;i)for(int j1;jm;j)scanf(%d,a[i][j]);f[1][1][v[s/a[1][1]]]1;for(int i1;in;i){memset(f[~i1],0,sizeof(f[~i1]));for(int j1;jm;j)for(int k1;kcnt;k){int znum[k];if(!f[i1][j][k]) continue;if(inz/a[i1][j]0) (f[~i1][j][v[z/a[i1][j]]]f[i1][j][k])%XJQ;if(jmz/a[i][j1]0) (f[i1][j1][v[z/a[i][j1]]]f[i1][j][k])%XJQ;}}for(int k1;kcnt;k)(ansf[n1][m][k])%XJQ;printf(%d,(c[n][m]-ansXJQ)%XJQ);
}
