正题

---

题目大意

$n\ast m$的矩阵有不同的权值，每次只可以往下走或往右走。要求走奇数次，要求偶数次经过的点和奇数次经过的点同余$K$

---

解题思路

设$f_{i,j,k,0/1}$表示在第$i$行$j$列，两个数只差为$k$，是奇数次还是偶数次。

然后

$$f_{i,j,k,0}=\sum \{\begin{array}{cc}{f}_{i-1,j,(k-a_{i,j}+k)\%K}& \\ f_{i,j-1,(k-a_{i,j}+k)\%K}& \end{array}$$

$$f_{i,j,k,1}=\sum \{\begin{array}{cc}{f}_{i-1,j,(k+a_{i,j})\%K}& \\ f_{i,j-1,(k+a_{i,j})\%K}& \end{array}$$

---

$code$

#include<cstdio> using namespace std; const int N=801,XJQ=1e9+7; int n,m,K,a[N][N],f[N][N][20][2]; int ans; int main() {scanf("%d%d%d",&n,&m,&K);K++;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j][a[i][j]%K][0]=1;for(int k=0;k<=K;k++){(f[i][j][k][0]+=f[i-1][j][(k-a[i][j]+K)%K][1])%=XJQ;(f[i][j][k][0]+=f[i][j-1][(k-a[i][j]+K)%K][1])%=XJQ;(f[i][j][k][1]+=f[i-1][j][(k+a[i][j])%K][0])%=XJQ;(f[i][j][k][1]+=f[i][j-1][(k+a[i][j])%K][0])%=XJQ;}(ans+=f[i][j][0][1])%=XJQ;}printf("%d",ans); }

总结

以上是生活随笔为你收集整理的P1373-小a和uim之大逃离【dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。