AGC013D Piling Up

Luogu

AtCoder

分析

设 $f[i][j]$ 表示前 $i$ 轮,还剩 $j$ 个红球的方案数。显然蓝球有 $n-j$ 个。

然而这样子是有重复计算的。

假如一个初始状态有 $x$ 个红球,转移过程中始终没有红球数量变为 $0$ 的时刻,那么就一定存在一个有 $y\;(y<x)$ 个红球的初始状态,它的转移过程与前者完全相同。

那么一个状态是不重复的,当且仅当转移过程中有某个时刻红球数量变为 $0$。

于是设 $f[i][j][0/1]$ 表示前 $i$ 轮,还剩 $j$ 个红球,是否达到过 $0$ 的方案数。

转移分四种情况考虑即可,比较简单。

最后答案为 $\sum\limits_{i=0}^nf[m+1][i][1]$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#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*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;
const int mod=1e9+7;

inline void add(int& x,int y) { x+=y; if (x>=mod) x-=mod; }

int f[N][N][2];

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;++i) f[1][i][0]=1;
    f[1][0][1]=1;
    for (re int i=1;i<=m;++i)
        for (re int j=0;j<=n;++j) {
            if (j>=1) { //红红
                if (j==1) add(f[i+1][j-1][1],f[i][j][0]);
                else add(f[i+1][j-1][0],f[i][j][0]);
                add(f[i+1][j-1][1],f[i][j][1]);
            }
            if (j<n) { //蓝蓝
                add(f[i+1][j+1][0],f[i][j][0]);
                add(f[i+1][j+1][1],f[i][j][1]);
            }
            if (j>=1) { //红蓝
                if (j==1) add(f[i+1][j][1],f[i][j][0]);
                else add(f[i+1][j][0],f[i][j][0]);
                add(f[i+1][j][1],f[i][j][1]);
            }
            if (j<n) { //蓝红
                add(f[i+1][j][0],f[i][j][0]);
                add(f[i+1][j][1],f[i][j][1]);
            }
        }
    int ans=0;
    for (re int i=0;i<=n;++i) add(ans,f[m+1][i][1]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 22 PM

发表评论