[AGC013D] Piling Up 题解

题意：

一开始有 $n$ 个颜色为黑白的球，但不知道黑白色分别有多少。

$m$ 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，

最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种。

答案对 $10^9+7$ 取模。

数据范围：

$1 \le n, m \le 3000$ 。

考虑设黑球初始有 $x_0$ 个，则白球有 $n - x_0$ 个。

记 $x_i$ 为 $i$ 次操作后的黑球数量，考察 $i+1$ 的每种情况：

两次都取黑球，要求 $x_i > 0$ ，有 $x_{i+1} = x_i -1$ 。
先黑球后白球，要求 $x_i > 0$ ，有 $x_{i+1} = x_i$ 。
先白球后黑球，要求 $x_i < n$ ，有 $x_{i+1}=x_i$ 。
两次都取白球，要求 $x_i < n$ ，有 $x_{i+1} = x_i + 1$ 。

那么对于一种操作序列，根据以上关系式，我们可以确定 $x_0$ 的区间。

考虑设 $f(i,j)$ 为 $x_i=j$ 时前 $i$ 次操作的合法方案数。

初始 $f(0,j) = 1$ ，答案为 $\sum f(n,j)$ 。转移显然。

不过这样的 dp 是会算重的，当 $x_0$ 的合法区间长度不为 $1$ 时，就可能统计到其他的情况。

考虑重新设 $f(i,j)$ 为 $x_i = j$ 时前 $i$ 次操作的合法方案数，要求 $j$ 没有达到过 $0$ 。

同时设 $g(i,j)$ 为 $x_i = j$ 时前前 $i$ 次操作的合法方案数，不过要求 $j$ 至少达到过一次 $0$ 。

答案就是 $\sum g(n,j)$ 。这样我们对于每个区间只统计了一次，于是这题就做完了

时间复杂度 $\mathcal{O}(nm)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const int mod = 1e9 + 7;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
template<typename T> T Add(T x, T y) { return (x + y) >= mod ? x + y - mod : x + y; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(3e3 + 15))

int n, m; ll res, f[2][N], g[2][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; g[0][0] = 1;
    rep(i, 1, n) f[0][i] = 1;
    rep(i, 1, m)
    {
        const int cur = i & 1, pre = cur ^ 1;
        rep(j, 0, n) f[cur][j] = g[cur][j] = 0;
        rep(j, 0, n)
        {
            if(j)
            {
                add(f[cur][j], f[pre][j - 1]);
                add(g[cur][j], Add(g[pre][j - 1], g[pre][j]));
                if(j == 1) add(g[cur][j], f[pre][j]);
                else add(f[cur][j], f[pre][j]);
            }
            if(j < n)
            {
                add(g[cur][j], Add(g[pre][j + 1], g[pre][j]));
                if(!j) add(g[cur][j], f[pre][j + 1]);
                else add(f[cur][j], Add(f[pre][j + 1], f[pre][j]));
            }
        }
    }
    rep(j, 0, n) add(res, g[m & 1][j]);
    cout << res << '\n';
    return 0;
}