「AGC021E」Ball Eat Chameleons

AGC021E - Ball Eat Chameleons

找不到对于第二种做法的详细描述，看到的都只有一个式子. 于是来写一下.

题意

有 $n$ 只变色龙，你会扔 $k$ 次球，球会被随机的一只变色龙吃掉. 球是蓝色或者红色的，初始时所有变色龙都是蓝色的，当一只变色龙吃下的红球和蓝球数量不同时它会变成较多的那种颜色.

你可以决定每次扔下球的颜色，求有多少种方案有可能使所有变色龙都变红. 两种方案不同当且仅当某一次扔下的球的颜色不同.

$1\le n,k \le 5\times 10^5$

做法 1

突然懒了，可以看官方题解.

做法 2

做法 1 通过奇偶讨论和组合数裂项也可以化简成这样. 这里提供一种（也许）更直观的理解.

下面令 $R$ 表示红色的、红球、红球的数量等，$B$ 同理.

考虑对于一个确定的序列和 $n$ 判断是否可行. 由于我们希望最终所有变色龙都变成 $R$，对于 $B$ 的情况，如果存在一只变色龙吃的 $R>B$，则可以把 $B$ 给它，否则可以把 $B$ 给一只钦定的变色龙（使大于一只变色龙吃的 $B>R$ 不优的，因为使它们要变成 $R$ 需要额外的 $R$）. 对于 $R$，只会给 $B$ 变色龙.

因此对于一个序列，可以使 $n$ 只变色龙变成 $R$ 当且仅当：

• 其包含至少 $n-1$ 个 $R$.
• 任意选出 $n-1$ 个 $R$ 与右侧尽量接近的 $B$ 匹配，每个 $B$ 只能被匹配一次，如果不存在则不匹配，匹配是唯一的. 存在一种方案使得，原序列删除这些 $R$ 和 $B$ 之后的序列中 $R>B$ 或 $R=B$ 且最后一个元素是 $B$.

下面设 $n$ 是最大的 $n$ 使得序列能使 $n$ 只变色龙变成 $R$. 设序列长度是 $k$. 假设一种上述的选择 $n-1$ 个 $R$ 的方案中某个 $R$ 到它对应的 $B$ 之间存在 $R$ 没有被选中，用后者替换前者，方案仍是合法的，因此下面我们只考虑每个 $R$ 都是极靠后的方案.

在序列的前 $k-1$ 个位置中选择 $n-1$ 个 $R$，由于满足了上述条件，可以推出其匹配的 $B$ 的位置集合，现在证明，在这些位置确定后，恰好存在一种方案使得序列至多能使 $n$ 只变色龙变成 $R$.

• 若余下的位置有奇数个，方案形如 $BB\dots RR\dots$，且 $R=B+1$

因为 $R+B$ 是奇数，所以 $B$ 和 $R$ 奇偶性不同.

• 若 $R \ge B+3$，则选中最后一个 $R$ 也是合法的，$n$ 不是最大的，矛盾.
• 若 $R<B$，则不合法.

因此 $R=B+1$.

若存在形如 $RB$ 的两项，则选中这个 $R$ 也是合法的，$n$ 不是最大的，矛盾.

因此方案形如 $BB\dots RR\dots$

• 若余下的位置有偶数个，方案形如 $BB\dots RR \dots B$，且 $R=B$.

因为 $R+B$ 是偶数，所以 $B$ 和 $R$ 奇偶性相同.

• 若 $R \ge B+2$，则选择最后一个 $R$ 也是合法的，$n$ 不是最大的，矛盾.
• 若 $R<B$，则不合法.

因此 $R=B$.

若最后一位不是 $B$ 则不合法. 若在前面存在形如 $RB$ 的两项，则选中这个 $R$ 也是合法的，$n$ 不是最大的，矛盾.

因此方案形如 $BB\dots RR \dots B$

不同的选择位置集合显然对应不同的答案序列，因此至多能使 $n$ 只变色龙变成 $R$ 的序列数量是 $\binom{k-1}{n-1}$，题目的答案即为 $\sum_{i=n}^k \binom{k-1}{i-1}$.

代码

#include<cstdio>

using namespace std;
#define ll long long

const int N = 500005, P = 998244353;
int n, k, ans, fac[N], ifac[N];
int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
int main() {
	scanf("%d%d", &n, &k);
	fac[0]=1;
	for(int i=1; i<=k; ++i) fac[i]=(ll)fac[i-1]*i%P;
	ifac[k]=Pow(fac[k]);
	for(int i=k; i; --i) ifac[i-1]=(ll)ifac[i]*i%P;
	for(int i=n; i<=k; ++i) ans=(ans+(ll)fac[k-1]*ifac[i-1]%P*ifac[k-i])%P;
	printf("%d\n", ans);
	return 0;
}