题目大意
地面上出现了一个n*m的巨幅矩阵，矩阵的每个格子上有一坨0~k不等量的魔液。怪物各给了小a和uim一个魔瓶，说道，你们可以从矩阵的任一个格子开始，每次向右或向下走一步，从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液，下一步由uim吸收，如此交替下去，并且要求最后一步必须由uim吸收。魔瓶只有k的容量，也就是说，如果装了k+1那么魔瓶会被清空成零，如果装了k+2就只剩下1，依次类推。问使两个人内的魔瓶内的魔液一样多的走法有多少种。
题解
我们很容易想到动规。用f(i, j, t, k, p)表示在位置(i, j)，小a瓶子里有t个魔液，uim瓶子里有k个魔液，p表示当前轮到小a还是uim。一开始我想枚举每一个起始点然后动规，这样的时间复杂度是$O(n^2 m^2 k)$的，这种转移的过程让我在潜意识里认为这道题就应该用Bfs解决，以至于随后想到可以将所有出发点一起整时就是n*m个Bfs同时做，时间复杂度$O(n^2m^2)$。请你想想，这究竟是动规还是暴力呀？
正确做法是：t和k可以转化为小a和uim瓶子里的液体的差d，这就降了一维；随后我们列出递归式来，根据递归式老老实实刷表即可。
一些卡常数：要mod K，请(x + k) % k即可，不要(x % k + k) % k，这就慢了；同时，也不要为了取模单独写一个函数，函数调用费时间。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
const int MAX_ROW = 810, MAX_COL = 810, MAX_K = 20;
const long long P = 1000000007;
int TotRow, TotCol, K;
int A[MAX_ROW][MAX_COL];
long long DP()
{
static int F[MAX_ROW][MAX_COL][MAX_K][2];
K++;
for (int row = 1; row <= TotRow; row++)
for (int col = 1; col <= TotCol; col++)
F[row][col][A[row][col]][0] = 1;
for (int row = 1; row <= TotRow; row++)
for (int col = 1; col <= TotCol; col++)
for (int t = 0; t < K; t++)
{
//当前是小a，下一个是uim
F[row + 1][col][(t - A[row + 1][col] + K) % K][1] += F[row][col][t][0];
F[row + 1][col][(t - A[row + 1][col] + K) % K][1] %= P;
F[row][col + 1][(t - A[row][col + 1] + K) % K][1] += F[row][col][t][0];
F[row][col + 1][(t - A[row][col + 1] + K) % K][1] %= P;
//当前是uim，下一个是小a
F[row + 1][col][(t + A[row + 1][col] + K) % K][0] += F[row][col][t][1];
F[row + 1][col][(t + A[row + 1][col] + K) % K][0] %= P;
F[row][col + 1][(t + A[row][col + 1] + K) % K][0] += F[row][col][t][1];
F[row][col + 1][(t + A[row][col + 1] + K) % K][0] %= P;
}
long long ans = 0;
for (int row = 1; row <= TotRow; row++)
for (int col = 1; col <= TotCol; col++)
ans = (ans + F[row][col][0][1]) % P;
return ans;
}
int main()
{
scanf("%d%d%d", &TotRow, &TotCol, &K);
for (int i = 1; i <= TotRow; i++)
for (int j = 1; j <= TotCol; j++)
scanf("%d", &A[i][j]);
printf("%lld
", DP());
return 0;
}