一眼看过去就是 f[a的位置][b的位置][a的容量][b的容量][谁走] 嘛.
结果一算,时间空间复杂度都过不去..我好菜啊
题目只要求计算差值, 所以记录a - b差值即可.
注意这样定义的话差值可能为负数, 所以要找等价关系.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 8e2 + 5;
const int MAXK = 15 + 1;int f[MAXN][MAXN][MAXK][2];
int a[MAXN][MAXN];
int N, M, K;int main()
{cin>>N>>M>>K; ++K;for(int i = 1; i <= N; i++)for(int j = 1; j <= M; j++){scanf("%d", &a[i][j]);a[i][j] %= K;f[i][j][a[i][j]][0] = 1;}int ans = 0;for(int i = 1; i <= N; i++)for(int j = 1; j <= M; j++)for(int k = 0; k < K; k++){(f[i + 1][j][(k + a[i + 1][j]) % K][0] += f[i][j][k][1]) %= MOD;(f[i][j + 1][(k + a[i][j + 1]) % K][0] += f[i][j][k][1]) %= MOD;(f[i + 1][j][(k - a[i + 1][j] + K) % K][1] += f[i][j][k][0]) %= MOD;(f[i][j + 1][(k - a[i][j + 1] + K) % K][1] += f[i][j][k][0]) %= MOD;(ans += f[i][j][k][1] * (k == 0)) %= MOD;}cout<<ans<<endl;return 0;
}
