P1373-小a和uim之大逃离

 1 #include <bits/stdc++.h>
 2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
 3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
 4 #define INF 0x3f3f3f3f
 5 #define MOD 1000000007
 6 typedef long long ll;
 7 using namespace std;
 8 inline ll read()
 9 {
10     ll ans = 0;
11     char ch = getchar(), last = ' ';
12     while(!isdigit(ch)) last = ch, ch = getchar();
13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
14     if(last == '-') ans = -ans;
15     return ans;
16 }
17 inline void write(ll x)
18 {
19     if(x < 0) x = -x, putchar('-');
20     if(x >= 10) write(x / 10);
21     putchar(x % 10 + '0');
22 }
23 int n,m,k;
24 int a[801][801];
25 int dp[801][801][16][2];
26 int main()
27 {
28     n = read(), m = read(), k = read();
29     _for(i,1,n+1)
30         _for(j,1,m+1)
31         {
32             a[i][j] = read();
33             dp[i][j][a[i][j]][0] = 1;
34         }
35     
36     k ++;
37     _for(i,1,n+1)
38         _for(j,1,m+1)
39             _for(p,0,k)
40             {
41                 if(i>=2)
42                 {
43                     dp[i][j][p][0] += dp[i-1][j][(p-a[i][j]+k)%k][1];
44                     dp[i][j][p][1] += dp[i-1][j][(p+a[i][j])%k][0];
45                 }
46                 if(j>=2)
47                 {
48                     dp[i][j][p][0] += dp[i][j-1][(p-a[i][j]+k)%k][1];
49                     dp[i][j][p][1] += dp[i][j-1][(p+a[i][j])%k][0];
50                 }
51                 dp[i][j][p][0] %= MOD;
52                 dp[i][j][p][1] %= MOD;
53             }
54     
55     int ans = 0;
56     _for(i,1,n+1)
57         _for(j,1,m+1)
58             ans += dp[i][j][0][1],ans %= MOD;
59     write(ans);
60     return 0;
61 }