题目链接：传送门
题目大意：
一个N行M列的矩阵，从任意点开始往右或者往下走，每走一格获得所到达的格子的分数。
要求总步数必须为偶数。问有多少种走法，使得奇数步得到的总分和偶数步得到的总分对K+1取模的值相等。
1 ≤ N, M ≤ 800, 1 ≤ K ≤ 15;
思路：
状态：
f[i][j][k]表示以（i，j）为终点时，奇数步与偶数步的差值为k时（当然k属于K+1的完全剩余系），的方案数。
初始状态：
若从（i-1，j）或（i，j-1）走到（i，j）时产生的差值为k，则f[i][j][k]++。
这是因为状态转移时只继承了之前的格子的状态，没有继承到之前没有格子的状态（第一步不用继承其他的状态）。
状态转移方程：
f[i+1][j+1][k1] += f[i][j][k]；其中k1 = k + 从（i， j）走到（i+1，j+1）时，产生的奇偶步差值。
（PS：这里有→↓和↓→两种走法）
f[i+2][j][k3] += f[i][j][k]；其中k3 = k + 从（i， j）走到（i+2，j）时，产生的奇偶步差值。
f[i][j+2][k4] += f[i][j][k]；其中k4 = k + 从（i， j）走到（i，j+2）时，产生的奇偶步差值。
当然以上的种种都要取模。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 800 + 1;
const int MOD = 1000000000 + 7;
#define mod(x) (x)%MOD
#define modk(x) ((x)+K)%K
#define dep1 mat[i+1][j]-mat[i+1][j+1]
#define dep2 mat[i][j+1]-mat[i+1][j+1]
#define dep3 mat[i+1][j]-mat[i+2][j]
#define dep4 mat[i][j+1]-mat[i][j+2]
int N, M, K;
int mat[MAX_N][MAX_N];
int f[MAX_N][MAX_N][16];
void init()
{
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (i >= 2)
f[i][j][modk(mat[i-1][j] - mat[i][j])]++;
if (j >= 2)
f[i][j][modk(mat[i][j-1] - mat[i][j])]++;
}
}
}
void dp()
{
init();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
for (int k = 0; k < K; k++) {
if (i+1 <= N && j+1 <= M) {
f[i+1][j+1][modk(k+dep1)] = mod(f[i+1][j+1][modk(k+dep1)] + f[i][j][k]);
}
if (i+1 <= N && j+1 <= M) {
f[i+1][j+1][modk(k+dep2)] = mod(f[i+1][j+1][modk(k+dep2)] + f[i][j][k]);
}
if (i+2 <= N && j <= M) {
f[i+2][j][modk(k+dep3)] = mod(f[i+2][j][modk(k+dep3)] + f[i][j][k]);
}
if (i <= N && j+2 <= M) {
f[i][j+2][modk(k+dep4)] = mod(f[i][j+2][modk(k+dep4)] + f[i][j][k]);
}
}
}
}
ll res = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
res = mod(res + f[i][j][0]);
// for (int i = 1; i <= N; i++) {
// for (int j = 1; j <= M; j++) {
// cout << f[i][j][0] << ' ';
// }
// cout << endl;
// }
cout << res << endl;
return;
}
int main()
{
cin >> N >> M >> K;
K++;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) {
scanf("%d", &mat[i][j]);
mat[i][j] %= K;
}
dp();
return 0;
}