这道题可以很容易看出是一道dp（因为是在dp关卡里找的）
稍微想一下就可以yy出一个不错的状态：
f[i][j][k][0/1]代表走到了点(i,j)、膜液量相差k（小a-uim=k）、小a/uim最后取的情况数
坑一：
f[850][850][20][2]:Accepted 100 2.00s 103.31MB f[850][850][25][2]:Unaccepted 85 1.11s 125.00MB//MLE三个点
转移也很好办：一个点只可能从左边或者上边走来
int tmp=(c-mp[i][j]+k)%k; f[i][j][c][0]+=(f[i-1][j][tmp][1]%mod+f[i][j-1][tmp][1]%mod)%mod; f[i][j][c][0]%=mod; tmp=(c+mp[i][j])%k; f[i][j][c][1]+=(f[i-1][j][tmp][0]%mod+f[i][j-1][tmp][0]%mod)%mod; f[i][j][c][1]%=mod;
其中tmp代表上一个点的膜液差
坑二：输入时的膜液量可能大于k
坑三：可以从任一点出发，应将每个f[i][j][mp[i][j]][0]赋值为1
坑四：c-mp[i][j]可能是负的，如果不写成tmp=(c-mp[i][j]+k)%k而是tmp=(c-mp[i][j])%k的话，
Unaccepted 10 2.01s 103.01MB
不多说了，看代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,k,mp[850][850]; 4 //坑一：炸空间 5 int f[850][850][20][2],sum; 6 #define mod 1000000007 7 int main(){ 8 ios::sync_with_stdio(0); 9 cin>>n>>m>>k; 10 k++; 11 //读入 12 for(int i=1;i<=n;i++){ 13 for(int j=1;j<=m;j++){ 14 cin>>mp[i][j]; 15 //坑二：膜液量 16 mp[i][j]%=k; 17 //坑三：出发点 18 f[i][j][mp[i][j]][0]=1; 19 } 20 } 21 //DP 22 for(int i=1;i<=n;i++){ 23 for(int j=1;j<=m;j++){ 24 for(int c=0;c<k;c++){ 25 //坑四：取膜 26 int tmp=(c-mp[i][j]+k)%k; 27 f[i][j][c][0]+=(f[i-1][j][tmp][1]%mod+f[i][j-1][tmp][1]%mod)%mod; 28 f[i][j][c][0]%=mod; 29 30 tmp=(c+mp[i][j])%k; 31 f[i][j][c][1]+=(f[i-1][j][tmp][0]%mod+f[i][j-1][tmp][0]%mod)%mod; 32 f[i][j][c][1]%=mod; 33 } 34 sum=(sum+f[i][j][0][1])%mod; 35 } 36 } 37 cout<<sum<<endl; 38 return 0; 39 }
完结撒花