小a和uim之大逃离

题意

有一矩阵，每个格子上有一坨0~k不等量的魔液，小a和uim以从矩阵的任一个格子开始，每次向右或向下走一步，从任一个格子结束。

魔瓶只有k的容量，若使结束时两瓶内魔液相等，有多少种方法。

题解

dp方程如下

    dp[i][j][h][0]+=dp[i-1][j][(h-a[i][j]+k)%k][1];
    dp[i][j][h][0]%=mod;
    dp[i][j][h][0]+=dp[i][j-1][(h-a[i][j]+k)%k][1];
    dp[i][j][h][0]%=mod;

    dp[i][j][h][1]+=dp[i-1][j][(h+a[i][j]+k)%k][0];
    dp[i][j][h][1]%=mod;
    dp[i][j][h][1]+=dp[i][j-1][(h+a[i][j]+k)%k][0];
    dp[i][j][h][1]%=mod;

调试记录

1.数组开大了MLE

2.符号打错了（逃）

#include 
#include 
#include 
using namespace std;
int dp[801][801][20][2];
int n,m,k,a[1000][1000];
long long ans=0;
const int mod=1000000007;
int main(){
    memset(dp,0,sizeof(dp));
    cin>>n>>m>>k;
    k++;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            cin>>a[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            dp[i][j][a[i][j]%k][0]=1;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int h=0;h<=k;h++){
            dp[i][j][h][0]+=dp[i-1][j][(h-a[i][j]+k)%k][1];
            dp[i][j][h][0]%=mod;
            dp[i][j][h][0]+=dp[i][j-1][(h-a[i][j]+k)%k][1];
            dp[i][j][h][0]%=mod;

            dp[i][j][h][1]+=dp[i-1][j][(h+a[i][j]+k)%k][0];
            dp[i][j][h][1]%=mod;
            dp[i][j][h][1]+=dp[i][j-1][(h+a[i][j]+k)%k][0];
            dp[i][j][h][1]%=mod;
            }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        ans+=dp[i][j][0][1],ans%=mod;
    cout<<ans;
    return 0;
}