【常规dp】P1373 小a和uim之大逃离

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 int a[810][810];
 7 int f[810][810][20][2];
 8 const int mod = 1e9 + 7;
 9 
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     int n, m;
14     int k;
15     cin >> n >> m >> k;
16     k++;
17     for (int i = 1; i <= n; i++)
18         for (int j = 1; j <= m; j++)
19         {
20             cin >> a[i][j];
21             f[i][j][a[i][j] % k][0] = 1;
22         }
23     for (int i = 1; i <= n; i++)
24         for (int j = 1; j <= m; j++)
25             for (int h = 0; h <= k; h++)
26             {
27                 f[i][j][h][0] = (f[i][j][h][0] + f[i - 1][j][(h - a[i][j] + k) % k][1]) % mod;
28                 f[i][j][h][0] = (f[i][j][h][0] + f[i][j - 1][(h - a[i][j] + k) % k][1]) % mod;
29                 f[i][j][h][1] = (f[i][j][h][1] + f[i - 1][j][(h + a[i][j]) % k][0]) % mod;
30                 f[i][j][h][1] = (f[i][j][h][1] + f[i][j - 1][(h + a[i][j]) % k][0]) % mod;
31             }
32     int sum = 0;
33     for (int i = 1; i <= n; i++)
34     {
35         for (int j = 1; j <= m; j++)
36         {
37             sum = (sum + f[i][j][0][1]) % mod;
38         }
39     }
40     cout<<sum;
41 }