目录
显示
题目链接
https://www.luogu.org/problem/P1373
题解
很容易设计这样一个状态:\(f(i,j,l_1,l_2,0/1)\) 代表当前位置 \((i,j)\),两人收集的液体分别为 \(l_1,l_2\) ,该步由小 A 或 uim 吸收时的方案数。
然而空间开不下…注意到两人收集到的液体多少并不重要,重要的是两人收集液体的差值。于是我们可以把中间的两维压缩成一维(即两人收集液体的差值),这样空间就在允许范围之内了。
接下来枚举当前位置和差值递推即可。
需要注意的是,液体量是对 \(k+1\) 而不是对 \(k\) 取模。
#include <iostream> #define MOD 1000000007 using namespace std; int f[805][805][20][2],a[805][805],ans; int main() { int n,m,k; cin>>n>>m>>k; k++; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; f[i][j][a[i][j]%k][0]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int l=0;l<=k;l++) { f[i][j][l][0]=(f[i][j][l][0]+f[i][j-1][(l-a[i][j]+k)%k][1])%MOD; f[i][j][l][0]=(f[i][j][l][0]+f[i-1][j][(l-a[i][j]+k)%k][1])%MOD; f[i][j][l][1]=(f[i][j][l][1]+f[i][j-1][(l+a[i][j])%k][0])%MOD; f[i][j][l][1]=(f[i][j][l][1]+f[i-1][j][(l+a[i][j])%k][0])%MOD; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=(ans+f[i][j][0][1])%MOD; cout<<ans<<endl; return 0; }