P1373 小a和uim之大逃离

f[i][j][p][0/1]表示到(i,j)时两人差为p且最后一步是0/1走的的方案数,

初始f[i][j][a[i][j]][0]=1

ans=sum{f[i][j][0][1]}

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}
const int mod=1e9+7;
const int N=805;
int n,m,k,f[N][N][18][2],a[N][N];
long long ans;
signed main(){
    read(n);read(m);read(k);k++;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            read(a[i][j]);
            f[i][j][a[i][j]][0]=1;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int p=0;p<k;p++){
                if(i>1){
                    (f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)%k][1])%=mod;
                    (f[i][j][p][1]+=f[i-1][j][(p+a[i][j])%k][0])%=mod;
                }
                if(j>1){
                    (f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)%k][1])%=mod;
                    (f[i][j][p][1]+=f[i][j-1][(p+a[i][j])%k][0])%=mod;
                }
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            (ans+=f[i][j][0][1])%=mod;
    write(ans);        
}