传送门：

---

定义状态是：\(f[i][j][h][0..1]\)表示在\([i,j]\)两个人相差为h，让某一个人走的方案数。（0表示小a，1表示uim）。

我们让小a走，那么状态转移方程就是\(f[i][j][h][0]=f[i][j][h][0]+f[i-1][j][(h-a[i][j]+k)mod \ k][1]+f[i][j-1][(h-a[i][j]+k)mod \ k][1]\)这里防止状态里面出现负数，就加模取模，这里的意思就是小a的状态必须是由先让uim走来的，那么这样原来的差距更小。

同理：\(f[i][j][h][1]=f[i][j][h][1]+f[i-1][j][(h+a[i][j])mod \ k][0]+f[i][j-1][(h+a[i][j]) mod \ k][0]\)，也就是前一个人走。

#include 
    
     #define ll long long#define ms(a, b) memset(a, b, sizeof(a))#define inf 0x3f3f3f3f#define mod 1000000007#define N 805using namespace std;template 
     
      inline void read(T &x) {    x = 0; T fl = 1;    char ch = 0;    while (ch < '0' || ch > '9') {        if (ch == '-') fl = -1;        ch = getchar();    }    while (ch >= '0' && ch <= '9') {        x = (x << 1) + (x << 3) + (ch ^ 48);        ch = getchar();    }    x *= fl;}int n, m, k;int a[N][N];int f[N][N][20][2];int 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] % k][0] = 1;        }    }    for (int i = 1; i <= n; i ++) {        for (int j = 1; j <= m; j ++) {            for (int h = 0; h <= k; h ++) {                f[i][j][h][0] = (f[i][j][h][0] + f[i - 1][j][(h - a[i][j] + k) % k][1] + f[i][j - 1][(h - a[i][j] + k) % k][1]) % mod;                f[i][j][h][1] = (f[i][j][h][1] + f[i - 1][j][(h + a[i][j]) % k][0] + f[i][j - 1][(h + a[i][j]) % k][0]) % mod;            }        }    }    int ans = 0;    for (int i = 1; i <= n; i ++) {        for (int j = 1; j <= m; j ++) {            ans = (ans + f[i][j][0][1]) % mod;        }    }    printf("%d\n", ans);    return 0;}