洛谷P1373 小a和uim之大逃离【线性dp】

题目：https://www.luogu.org/problemnew/show/P1373

题意：

有一个n*m的地图，每个点上有一个数值。两个人在任一点开始任一点结束，只能往右或往下走，轮流收集数值。

超过k+1时会清零。问使得他们最后收集到的数值相等的方案数。

思路：

每次状态数一多再牵扯到方案数就开始懵。其实这道题也不怎么难。

$dp[i][j][h][0]$表示走到$(i,j)$,差值是$h$且最后一步是小a时的方案数。

//#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue> 
#include<map>
#include<stack>
#include<set>

#define LL __int128
#define ull unsigned long long
#define inf 0x7f7f7f7f 

using namespace std;

int n, m, k;
const int maxn = 805;
const int mod = 1e9+7;
int num[maxn][maxn];
int dp[maxn][maxn][20][2];

int main()
{
    scanf("%d%d%d", &n, &m, &k);k++;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &num[i][j]);
            dp[i][j][num[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][j][h][0] + dp[i][j - 1][(h - num[i][j] + k) % k][1]) % mod;
                dp[i][j][h][0] = (dp[i][j][h][0] + dp[i - 1][j][(h - num[i][j] + k) % k][1]) % mod; 
                dp[i][j][h][1] = (dp[i][j][h][1] + dp[i][j - 1][(h + num[i][j]) % k][0]) % mod;
                dp[i][j][h][1] = (dp[i][j][h][1] + dp[i - 1][j][(h + num[i][j]) % k][0]) % mod;
            }
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ans = (ans + dp[i][j][0][1]) % mod;
        }
    }
    printf("%d
", ans);
    return 0;    
}