luogu 1373 小a和uim之大逃离 dp

有取模操作，所以直接维护模意义下的差即可. 

Code: 

#include <bits/stdc++.h>  
#define M 16  
#define N 801    
#define ll long long 
#define mod 1000000007  
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int v[N][N];   
int dp[N][N][M][2];      
void add(int &a,int b) 
{
    ll c=(1ll*a+1ll*b+mod)%mod ;   
    a=(int)c;   
}
int main() 
{ 
    int n,m,k,i,j;
    // setIO("input");         
    scanf("%d%d%d",&n,&m,&k), ++k;     
    for(i=1;i<=n;++i) 
        for(j=1;j<=m;++j) scanf("%d",&v[i][j]);      
    for(i=1;i<=n;++i) 
        for(j=1;j<=m;++j) dp[i][j][v[i][j]%k][0]=1;            
    for(i=1;i<=n;++i) 
    {
        for(j=1;j<=m;++j) 
        { 
            for(int d=0;d<k;++d) 
            { 
                if(i-1>=1) 
                {        
                    add(dp[i][j][d][0], dp[i-1][j][(d-v[i][j]+k)%k][1]);   
                    add(dp[i][j][d][1], dp[i-1][j][(d+v[i][j])%k][0]);             
                } 
                if(j-1>=1) 
                {  
                    add(dp[i][j][d][0], dp[i][j-1][(d-v[i][j]+k)%k][1]);   
                    add(dp[i][j][d][1], dp[i][j-1][(d+v[i][j])%k][0]);     
                }
            }
        }
    }
    int ans=0;   
    for(i=1;i<=n;++i) 
    {
        for(j=1;j<=m;++j) 
            add(ans, dp[i][j][0][1]);      
    }
    printf("%d
",ans);   
    return 0; 
}