Rockdu's Blog

Problem Statement

In Republic of AtCoder, Snuke Chameleons (Family: Chamaeleonidae, Genus: Bartaberia) are very popular pets. Ringo keeps $N$ Snuke Chameleons in a cage.

A Snuke Chameleon that has not eaten anything is blue. It changes its color according to the following rules:

• A Snuke Chameleon that is blue will change its color to red when the number of red balls it has eaten becomes strictly larger than the number of blue balls it has eaten.
• A Snuke Chameleon that is red will change its color to blue when the number of blue balls it has eaten becomes strictly larger than the number of red balls it has eaten.

Initially, every Snuke Chameleon had not eaten anything. Ringo fed them by repeating the following process $K$ times:

• Grab either a red ball or a blue ball.
• Throw that ball into the cage. Then, one of the chameleons eats it.

After Ringo threw in $K$ balls, all the chameleons were red. We are interested in the possible ways Ringo could have thrown in $K$ balls. How many such ways are there? Find the count modulo $998244353$. Here, two ways to throw in balls are considered different when there exists $i$ such that the color of the ball that are thrown in the $i$-th throw is different.

Constraints

• $1\le N,K\le 5\times {10}^5$
• $N$ and $K$ are integers.

Sample Input 1 Copy

2 4

Sample Output 1 Copy

7

We will use R to represent a red ball, and B to represent a blue ball. There are seven ways to throw in balls that satisfy the condition: BRRR, RBRB, RBRR, RRBB, RRBR, RRRB and RRRR.

Sample Input 2 Copy

3 7

Sample Output 2 Copy

57

Sample Input 3 Copy

8 3

Sample Output 3 Copy

0

Sample Input 4 Copy

8 10

Sample Output 4 Copy

46

Sample Input 5 Copy

123456 234567

Sample Output 5 Copy

857617983​​

 题目大意：你有N只变色龙，K个球。每一个球你可以刷成蓝的或者刷成红的，然后依次给这些变色龙吃。一个变色龙只有在它吃到的红球大于蓝球或蓝球大于红球时才会变色。（也就是说如果先吃一个红球再吃一个蓝球，因为第一次吃到红球所以它变成红色，再吃蓝球蓝红都是1个不变色，但如果再吃一个蓝球那么它就变成蓝色。）。问有多少中合法的球的颜色顺序，可以通过合理的分发给不同的变色龙使它们都变为红色。

首先，考虑如何验证一个球的顺序是否合法。

我们这样构造：如果一开始就有连续的蓝球，我们找一个倒霉的变色龙把它吃完。之后每有红球我们就分给其他的一个变色龙，并且注意到只吃一个红球的变色龙是可以白白再吃一个蓝球的。所以后面的蓝球我们先给只吃了一个红球的变色龙吃。直到其他所有变色龙都吃了一个蓝球一个红球。这时我们开始抢救那只倒霉的变色龙，把后面所有蓝的和红的都给他看合不合法就行了。不难理解这样一定是最优的。

并且有个显然的道理，如果一个序列可以满足使x个变色龙变红，那么它也一定满足使小于x个的变色龙变红。

那么我们只要快速算出一定能使x个变色龙变红的方案数即可。

而这个方案数其实就是组合数k - 1选x - 1，这是为什么呢？

我们想象先拿出一个球来不动，然后我们从剩下的里面选出x - 1个球作为红球，作为给除了倒霉变色龙外的变色龙变红的球，此时我们一定可以通过牺牲倒霉变色龙来使得这些变色龙都吃了一个红球一个蓝球。之后倒霉的变色龙怎么办呢？不要忘了我们开始拿出了一个球，现在我们钦定它是红的，并且喂给倒霉变色龙，是不是就合法了~~~~

所以我们只需要把一定能使大于等于n的变色龙变红的方案数加起来就完了，变成了组合数模板。

#include<cstdio>
#define LL long long
#define __debug
using namespace std;
const int maxn = 5e5 + 5, mod = 998244353;
int step[maxn], inv[maxn];
 
LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}
 
void pre(int n) {
	step[0] = inv[0] = 1;
	for(register int i = 1; i <= n; ++i) 
		step[i] = 1ll * step[i - 1] * i % mod;
	inv[n] = fpow(step[n], mod - 2);
	for(register int i = n - 1; i >= 1; --i)
		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
 
int C(int n, int m) {
	if(n < 0) return m & 1 ? -C(m - n - 1, m) : C(m - n - 1, m);
	if(n - m < 0) return 0;
	return (1ll * step[n] * inv[n - m] % mod) * inv[m] % mod;
}
 
int n, k, ret;
int main() {
	scanf("%d%d", &n, &k), pre(k);
	if(n > k) return printf("0"), 0;
	for(register int i = n; i <= k; ++i) {
		ret += C(k - 1, i - 1) % mod, ret %= mod;
	}
	printf("%d", ret);
	return 0;
}