做题记录整理dp7 P1373 小a和uim之大逃离（2022/9/20）

P1373 小a和uim之大逃离

好吧，这道题是看题解的。。。（dp学得是真的拉）

不过看的是kksc03这种无代码的，应该也还行。。。

#include <bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
const int inf = 1e9;
int dp[805][805][18][2];
int n, m, k;
int a[805][805];
int ans;
const int mod = 1e9 + 7;

int main() {
    scanf("%d%d%d", &n, &m, &k);
    ++k;
    for1(i, 1, n)
    for1(j, 1, m)
    scanf("%d", &a[i][j]),
          dp[i][j][a[i][j] % k][0] = 1;

    for1(i, 1, n) {
        for1(j, 1, m) {
            for1(l, 0, k) {
                dp[i][j][l][0] = (dp[i][j][l][0] + dp[i - 1][j][(l - a[i][j] + k) % k][1]) % mod;
                dp[i][j][l][0] = (dp[i][j][l][0] + dp[i][j - 1][(l - a[i][j] + k) % k][1]) % mod;
                dp[i][j][l][1] = (dp[i][j][l][1] + dp[i - 1][j][(l + a[i][j]) % k][0]) % mod;
                dp[i][j][l][1] = (dp[i][j][l][1] + dp[i][j - 1][(l + a[i][j]) % k][0]) % mod;
            }
        }
    }
    for1(i, 1, n)
    for1(j, 1, m)
    ans = (ans + dp[i][j][0][1]) % mod;
    printf("%d\n", ans);
    return 0;
}