斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1373 小a和uim之大逃离

posted on 2018-10-23 19:00:16 | under 刷题 |

P1373 小a和uim之大逃离

一开始以为是个组合数,心说:组合数是$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)$。

附代码:

#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;
}