[洛谷 1373]小a和uim之大逃离

题目链接

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;
}