P1373 小 a 和 uim 之大逃离

这是一道好的dp

---

题目链接：P1373 小 a 和 uim 之大逃离

题意：

小a和uim两个人是绑在一起走的
也就是说小a负责吸收第奇数次的魔液，而uim负责吸收偶数次的魔液
那么最终要求的是所有由uim结束吸收后两人魔瓶中魔液相等的方法

---

根据这个题意我们可以很好的列出状态转移方程

f(i,j,c,0/1)表示的是当两人走到i,j时差值为c的方案数(0代表现在为小a取，1代表为uim取)

那么我们来考虑一下状态转移方程该如何设计：

f(i,j,c,0)+=f(i-1,j,(c-val[i,j]+k)%k,1)

f(i,j,c,0)+=f(i,j-1,(c-val[i,j]+k)%k,1)

f(i,j,c,1)+=f(i-1,j,(c-val[i,j]+k)%k,0)

f(i,j,c,1)+=f(i,j-1,(c-val[i,j]+k)%k,0)

---

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
const int N=801,mod=1e9+7;int n,m,k;
int ans=0;
int val[N][N];
int f[N][N][20][2];int main()
{cin>>n>>m>>k;k++;rep(i,1,n)rep(j,1,m){cin>>val[i][j];f[i][j][val[i][j]%k][0]=1;}rep(i,1,n){rep(j,1,m){rep(c,0,k){f[i][j][c][0]=(f[i][j][c][0]+f[i-1][j][(c-val[i][j]+k)%k][1])%mod;f[i][j][c][0]=(f[i][j][c][0]+f[i][j-1][(c-val[i][j]+k)%k][1])%mod;f[i][j][c][1]=(f[i][j][c][1]+f[i-1][j][(c+val[i][j])%k][0])%mod;f[i][j][c][1]=(f[i][j][c][1]+f[i][j-1][(c+val[i][j])%k][0])%mod;}}}rep(i,1,n)rep(j,1,m){ans=(ans+f[i][j][0][1])%mod;}cout<<ans;return 0;
}