【洛谷1373】小a和uim之大逃离

2018-03-18 21:54:50

n,m<=800,1<=k<=15

md有毒吧

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int mo=(int)1e9+7;
int rd(){int z=0,mk=1;  char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
return z*mk;
}
int n,m,o,a[810][810];
int f[810][810][2][16];
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m>>o;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)  a[i][j]=rd()%mo;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
//f[i][j][1][o+a[i][j]]=1;
f[i][j][1][a[i][j]]=1;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
//for(int k=-o;k<=o;++k){
for(int k=0;k<=o;++k){
//f[i+1][j][0][o+(k-a[i+1][j])%(o+1)]=(f[i+1][j][0][o+(k-a[i+1][j])%(o+1)]+f[i][j][1][o+k])%mo;
f[i+1][j][0][(k-a[i+1][j]+o+1)%(o+1)]=(f[i+1][j][0][(k-a[i+1][j]+o+1)%(o+1)]+f[i][j][1][k])%mo;
f[i+1][j][1][(k+a[i+1][j])%(o+1)]=(f[i+1][j][1][(k+a[i+1][j])%(o+1)]+f[i][j][0][k])%mo;
//f[i][j+1][0][o+(k-a[i][j+1])%(o+1)]=(f[i][j+1][0][o+(k-a[i][j+1])%(o+1)]+f[i][j][1][o+k])%mo;
f[i][j+1][0][(k-a[i][j+1]+o+1)%(o+1)]=(f[i][j+1][0][(k-a[i][j+1]+o+1)%(o+1)]+f[i][j][1][k])%mo;
f[i][j+1][1][(k+a[i][j+1])%(o+1)]=(f[i][j+1][1][(k+a[i][j+1])%(o+1)]+f[i][j][0][k])%mo;
}
int bwl=0;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
bwl=(bwl+f[i][j][0][0])%mo;
//if(f[i][j][0][o])  cout<<i<<" "<<j<<endl;
}
cout<<bwl<<endl;
return 0;
}

• star
首页