【洛谷】【动态规划】小a和uim之大逃离

题目链接:https://www.luogu.org/problemnew/show/P1373

转移方程:$f[i][j][tmp][b]+=f[i][j][k][b$ $xor$ $1]+f[i][j][k][b$ $xor$ $1]$

假使$f[i][j][k][0]$代表走到$(i,j)$时由uim取,差值在模$mod$意义下为$k$的方案数,那么$ans=\sum_{i=1}^n\sum_{j=1}^m f[i][j][0][0]$

转移方程很好想,空间也是足够的,但这庞大的空间开销实在是太浪费了

我们观察方程发现某格的值只与上面一格、左面一格有关,于是我们压掉上面那一维,且在线统计

然后就得到了如下的代码↓

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=805,MOD=1e9+7;

int n,m,mod,ans,x;
int f[2][MAXN][16][2];

inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}

int main(){
    scanf("%d%d%d",&n,&m,&mod);++mod;
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            x=read();
            for(register int k=0;k<mod;++k) f[i&1][j][k][1]=f[i&1][j][k][0]=0;
            f[i&1][j][x][1]=1;
            for(register int k=0;k<mod;++k){
                int tmp1=(k-x+mod)%mod,tmp2=(k+x)%mod;
                int cmp1=f[i&1^1][j][k][1]+f[i&1][j-1][k][1],cmp2=f[i&1^1][j][k][0]+f[i&1][j-1][k][0];
                if(cmp1>=MOD) cmp1-=MOD;
                if(cmp2>=MOD) cmp2-=MOD;
                f[i&1][j][tmp1][0]+=cmp1;
                f[i&1][j][tmp2][1]+=cmp2;
                if(f[i&1][j][tmp1][0]>=MOD) f[i&1][j][tmp1][0]-=MOD;
                if(f[i&1][j][tmp2][1]>=MOD) f[i&1][j][tmp2][1]-=MOD;
            }ans+=f[i&1][j][0][0];
            if(ans>=MOD) ans-=MOD;
        }
    }printf("%d\n",ans);
    return 0;
}