[AGC013D] Piling Up 题解

题目链接：[AGC013D] Piling Up

题意：

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

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

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

答案对 \(10^9+7\) 取模。

数据范围：

\(1 \le n, m \le 3000\) 。

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

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

1. 两次都取黑球，要求 \(x_i > 0\) ，有 \(x_{i+1} = x_i -1\) 。
2. 先黑球后白球，要求 \(x_i > 0\) ，有 \(x_{i+1} = x_i\) 。
3. 先白球后黑球，要求 \(x_i < n\) ，有 \(x_{i+1}=x_i\) 。
4. 两次都取白球，要求 \(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;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/cy68zxln

[2] https://www.luogu.com.cn/article/rxlwqm73