洛谷1373 小a和uim之大逃离

Luogu

算法

DP。

用$f[i][j][p][0/1]$表示在(i,j)格,差值为k,小a或uim取的方案数。

那么可以得到这些状态转移:

$f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)\%k][1]$
$f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k]\%k][1]$
$f[i][j][p][1]+=f[i-1][j][(p+a[i][j])\%k][0]$
$f[i][j][p][1]+=f[i][j-1][(p+a[i][j])\%k][0]$

注意最后是uim取,那么答案为$\sum\{f[i][j][0][1]\}$。

注意取模。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int f[801][801][21][2]; //f[i][j][k][0/1]表示在(i,j)格,差值为k,小a或uim取的方案数
int a[801][801];
int n,m,k;
const int MOD=1000000007;
int main() {
    n=read(),m=read(),k=read()+1;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++) {
            a[i][j]=read();
            f[i][j][a[i][j]%k][0]=1; //初始化,因为小a可以从任意格子开始
        }
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++)
            for (re int p=0;p<=k;p++) {
                f[i][j][p][0]=(f[i][j][p][0]+f[i-1][j][(p-a[i][j]+k)%k][1])%MOD;
                f[i][j][p][0]=(f[i][j][p][0]+f[i][j-1][(p-a[i][j]+k)%k][1])%MOD;
                f[i][j][p][1]=(f[i][j][p][1]+f[i-1][j][(p+a[i][j])%k][0])%MOD;
                f[i][j][p][1]=(f[i][j][p][1]+f[i][j-1][(p+a[i][j])%k][0])%MOD;
            }
    int ans=0;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=m;j++)
            ans=(ans+f[i][j][0][1])%MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 12 : 59 PM

发表评论