AGC021-E Ball Eat Chameleons

题目大意

你有$n$只吃球的变色龙,每一只变色龙一开始都是蓝色的。
一只蓝色变色龙变成红色当且仅当其吃下的红色球数目严格大于蓝色球的数目。同理,一只红色变色龙变成蓝色当且仅当其吃下的蓝色球数目严格大于红色球的数目。
你要投喂$K$次,每一次你挑一种颜色的球,然后丢到笼子里给任意一个变色龙吃。
已知最后变色龙都变成了红色,求有多少种不同的颜色序列可能造成这一种情况(判重时并不考虑具体谁吃了,只考虑颜色)。

$1\leq n,K\leq5\times10^5$


题目分析

显然颜色序列合法当且仅当我们能将其划分成$n$个子序列,使得每一个子序列要么满足红球数目严格大于蓝球,要么满足红球数目与蓝球数目相等且最后一个球是蓝球。
令红球数目为$R$,蓝球数目为$B$。我们枚举红球数目,考虑数形结合,将红篮球的状态表示成二维平面上的点,要从$(0,0)$走正方向到某个位置。分下面两种情况讨论:

  • $R=B$,那么最后一个球一定是蓝色的。给定一个颜色序列,我们可以这样贪心匹配:先弄出$n$对红蓝两球,然后剩下的全部分给最后一对。那么其实就是从$(0,0)$走到$(R,B-1)$,并且不能经过$y-x\geq R-n+1$的点。
  • $R>B$,依然贪心匹配:先弄出$n-(R-B)$对红蓝两球,然后剩下的全部分给任意一个最终红球大于蓝球的序列。其实就是从$(0,0)$走到$(R,B)$,并且不能经过$y-x\geq R-n+1$的点。

直接用卡特兰数计算就好了。
时间复杂度$O(K)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>

using namespace std;

const int P=998244353;
const int L=1000000;

int fact[L+5],invf[L+5];
int n,K,ans;

inline int quick_power(int x,int y)
{
int ret=1;
for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ret=1ll*ret*x%P;
return ret;
}

void pre()
{
fact[0]=1;
for (int i=1;i<=L;++i) fact[i]=1ll*fact[i-1]*i%P;
invf[L]=quick_power(fact[L],P-2);
for (int i=L;i>=1;--i) invf[i-1]=1ll*invf[i]*i%P;
}

inline int C(int n,int m){return n>=m?1ll*fact[n]*invf[m]%P*invf[n-m]%P:0;}

inline int calc(int n,int m,int t)
{
if (m-n>=t||t<=0) return 0;
return (C(n+m,m)-C(n+m,n+t)+P)%P;
}

int main()
{
freopen("chameleons.in","r",stdin),freopen("chameleons.out","w",stdout);
pre(),scanf("%d%d",&n,&K),ans=0;
for (int R=K,B;R>=K-R&&R>=0;--R)
{
B=K-R;
if (R==B) (ans+=calc(R,B-1,R-n+1))%=P;
else (ans+=calc(R,B,R-n+1))%=P;
}
printf("%d\n",ans);
fclose(stdin),fclose(stdout);
return 0;
}