[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\) 的每种情况:
- 两次都取黑球,要求 \(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;
}
参考文献: