2017-08-13 19:22:31

### 思路分析

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
using namespace std;
const int MAXN = 800, MAXM = 800, MAXK = 15, MOD=1e9+7;
int N,M,K,n1,n2,Ans,W[MAXN+2][MAXM+2],opt[MAXN+2][MAXM+2][MAXK+2][2];//85MB
int f=1,r=0;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){r=r*10+c-'0';c=getchar();}
return f*r;
}
int main(){
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
for(int i=N;i>=1;i--)
for(int j=M;j>=1;j--)
for(int p=0;p<=K;p++) {
n1=(p+W[i][j])%(K+1);n2=(p-W[i][j]%(K+1)+((K+1)<<1))%(K+1);
//q=0
opt[i][j][p][0] = (opt[i][j][p][0]%MOD
+ opt[i+1][j][n1][1]%MOD) %MOD;
opt[i][j][p][0] = (opt[i][j][p][0]%MOD
+ opt[i][j+1][n1][1]%MOD) %MOD;
//q=1
opt[i][j][p][1]= (opt[i][j][p][1]%MOD
+ opt[i+1][j][n2][0]%MOD) %MOD;
opt[i][j][p][1] = (opt[i][j][p][1]%MOD
+ opt[i][j+1][n2][0]%MOD) %MOD;
//Stop here
if(n2==0) opt[i][j][p][1]++;
}
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
Ans=(Ans%MOD+opt[i][j][0][0]%MOD)%MOD;
printf("%d",Ans);
return 0;
}

• star
首页