Analysis
这一道题目，首先，因为是交替进行，所以要有一维来表示是两个人中的哪一个，其次，这是一个矩阵，还要有矩阵的位置，最后，因为只有双方的魔液数量相同的时候才可以活下来，所以说应该还有一维来记录双方魔液的差值。对于状态转移方程，先做出如下约定：
- 1->小A, 0->uim
- 差值为：小A的魔液减去uim的魔液
对于小A:
$$
f[i][j][k][1]+=f[i-1][j][(k-mat[i][j]+md)\mod md][0]\\
f[i][j][k][1]+=f[i][j-1][(k-mat[i][j]+md)\mod md][0]
$$
对于uim:
$$
f[i][j][k][0]+=f[i-1][j][(k+mat[i][j])\mod md][1]\\
f[i][j][k][0]+=f[i][j-1][(k+mat[i][j])\mod md][1]
$$
对于差值，如果说这一步是小A拿到魔液的话，那么双方的差值就应该增大，所以说这一步应该是从减去这么多魔液的地方转移过来的，同样如果说是uim拿到了魔液的话，双方的差值就会减少，所以说因该就是从增加了这么多魔液的地方转移过来的
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
#define mod 1000000007
#define maxn 802
using namespace std;
int mat[maxn][maxn];
int f[maxn][maxn][18][2];
int N,M,K;
int main(){
scanf("%d%d%d",&N,&M,&K);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
scanf("%d",&mat[i][j]);
mat[i][j]%=(K+1);
f[i][j][mat[i][j]][1]=1;
}
const int md=K+1;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
for(int del=0;del<=K;del++){
(f[i][j][del][1]+=f[i-1][j][(del-mat[i][j]+md)%md][0])%=mod;
(f[i][j][del][1]+=f[i][j-1][(del-mat[i][j]+md)%md][0])%=mod;
(f[i][j][del][0]+=f[i-1][j][(del+mat[i][j])%md][1])%=mod;
(f[i][j][del][0]+=f[i][j-1][(del+mat[i][j])%md][1])%=mod;
}
}
}
long long ans=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
(ans+=f[i][j][0][0])%=mod;
}
}
cout<<ans;
return 0;
}
|