P1373 小a和uim之大逃离

[P1373 小a和uim之大逃离](https://www.luogu.org/problemnew/show/P1373) 一开始以为是个组合数，心说：组合数是$DP$？好像只有杨辉三角是递推吧。。。 然后尴尬的发现题目看错了。。。药丸。。。 首先，这是个$DP$题，当然要设状态辣！ 设$dp[i][j][k][l][0/1]$表示走到$(i,j)$的方案数，$k$和$l$分别表示走到$(i,j)$时两个人的分数，$0/1$表示谁吸魔液。 但是这样需要枚举起点，四维再加两维，这是要$TLE$的节奏啊。。。 于是乎回头看题——题目只求方案数，而答案只和差值有关。 那把分数记下来有什么用？！ 而且同一个差值对应着多种情况转移而来，枚举所有差值解就是完全的了，起点枚举也免了！ 于是变成了： 设$dp[i][j][k][0/1]$表示走到$(i,j)$的方案数，$k$表示走到$(i,j)$时两个人分数差，$0/1$表示谁吸魔液。 转移方程就看代码吧。。。~~这里太小了写不下~~ 转移的时候对分数的差值加减之后取模即可。 复杂度$O(nmk)$。 附代码： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 803 #define MOD 1000000007LL using namespace std; int n,m,q; long long ans=0; int val[MAXN][MAXN],dp[MAXN][MAXN][17][2]; inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } void work(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<q;k++){ if(i+1==n){ dp[i+1][j][(k+val[i+1][j])%q][0]=(dp[i+1][j][(k+val[i+1][j])%q][0]+dp[i][j][k][1])%MOD; dp[i+1][j][(k-val[i+1][j]+q)%q][1]=(dp[i+1][j][(k-val[i+1][j]+q)%q][1]+dp[i][j][k][0])%MOD; } if(j+1==m){ dp[i][j+1][(k+val[i][j+1])%q][0]=(dp[i][j+1][(k+val[i][j+1])%q][0]+dp[i][j][k][1])%MOD; dp[i][j+1][(k-val[i][j+1]+q)%q][1]=(dp[i][j+1][(k-val[i][j+1]+q)%q][1]+dp[i][j][k][0])%MOD; } if(k==0)ans=(ans+dp[i][j][k][1])%MOD; } printf("%lld\n",ans); } void init(){ n=read();m=read();q=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ val[i][j]=read(); dp[i][j][val[i][j]%q][0]=1; } } int main(){ init(); work(); return 0; } ```