P1373-小a和uim之大逃离

亦凉 2023-06-01 08:52 6阅读 0赞

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 }

转载于:https://www.cnblogs.com/Asurudo/p/11407002.html