容易发现一个变色龙是红色当且仅当,设 \(R\) 为红球数量,\(B\) 为蓝球数量,那么 \(R \ge B\) 或 \(R = B\) 且最后一个球是蓝球。
考虑如何判定一个颜色序列是否可行。
考虑贪心。
- 若 \(R < B\) 显然不行。
- 若 \(R \ge B + n\),每个变色龙都可以分到比蓝球数多 \(1\) 的红球,答案为 \(\binom{R + B}{R}\)。
- 若 \(R = B\),考虑删除颜色序列中的最后一位(这一位必然是 \(\texttt{B}\)),转化为 \(B < R < B + n\) 的情况。
- 若 \(B < R < B + n\),考虑分配得尽量平均,每个变色龙分到的蓝球数恰好等于红球数或等于红球数减 \(1\)。那么每个蓝球数等于红球数的变色龙,我们贪心地给它分配 \(\texttt{RB}\) 即可,剩下的全部给蓝球数等于红球数或等于红球数减 \(1\) 的变色龙。
于是现在问题转化为了,求满足可以取出 \(n - (R - B)\) 个 \(\texttt{RB}\) 的 \(\texttt{RB}\) 序列。
考虑转化成,每个前缀的红球数减蓝球数不小于 \(n - (R - B) - B = n - R\),也就是说不能匹配的蓝球数 \(\le R - n\)。
考虑画出折线图,\(\texttt{R}\) 就是 \((x, y) \to (x + 1, y + 1)\),\(\texttt{B}\) 就是 \((x, y) \to (x + 1, y - 1)\)。那么就是要求从 \((0, 0)\) 走到 \((R + B, R - B)\) 且与 \(y = n - R - 1\) 没有交点的路径数。
考虑容斥,总路径数 \(\binom{R + B}{R}\) 减去与 \(y = n - R - 1\) 有交点的路径数。把在 \(y = n - R - 1\) 下方的折线翻上去,等价于从 \((0, 2n - 2R - 2)\) 到 \((R + B, R - B)\)。设 \(x\) 为向右上走的步数,\(y\) 为向右下走的步数,那么 \(x + y = R + B, x - y = 3R - B - 2n + 2\),可得 \(x = 2R - n + 1\)。所以,与 \(y = n - R - 1\) 有交点的路径数就是 \(\binom{x + y}{x} = \binom{R + B}{2R - n + 1}\)。
时间复杂度线性。
code
// Problem: E - Ball Eat Chameleons
// Contest: AtCoder - AtCoder Grand Contest 021
// URL: https://atcoder.jp/contests/agc021/tasks/agc021_e
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2000100;
const int N = 2000000;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, fac[maxn], ifac[maxn];
inline void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
ll ans = 0;
for (int i = n; i <= m; ++i) {
int j = m - i;
if (i < j) {
continue;
}
if (i >= j + n) {
ans = (ans + C(i + j, i)) % mod;
} else {
if (i == j) {
--j;
}
ans = (ans + C(i + j, i) - C(i + j, i * 2 - n + 1) + mod) % mod;
}
}
printf("%lld\n", ans);
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Chameleons AtCoder Contest Grand Ballchameleons atcoder contest grand authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 022 atcoder contest grand 001 atcoder contest descent grand histogram atcoder contest grand atcoder contest grand 019 atcoder contest grand 017