AGC021E Ball Eat Chameleons <组合数学>

Problem

Ball Eat Chameleons

$\mathrm{Time\;limit:\;2\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

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\le5\times10^5$
$N$ and $K$ are integers.

Input

Input is given from Standard Input in the following format:
$N\;K$

Output

Print the possible ways Ringo could have thrown in $K$ balls, modulo $998244353$.

Sample

Input #1

2 4

Output #1

7

Explanation #1
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.
Input #2

3 7

Output #2

57

Input #3

8 3

Output #3

0

Input #4

8 10

Output #4

46

Input #5

123456 234567

Output #5

857617983

标签：组合数学

Translation

有$n$只变色龙，每次可以选红色或蓝色的球给一只变色龙吃。每当一只变色龙吃的红色球严格大于蓝色球时，会变成蓝色，每当其吃的蓝色球严格大于红色球时，会变成红色。现在一共可以取$k$个球，问有多少种取球序列能使得最后所有变色龙都变成红色。两个取球序列$P,Q$不同当且仅当$\exist i,\;s.t.P_i\ne Q_i$。

Solution

一只变色龙最后变成红色当且仅当其吃的球的序列中满足一下之一：

• 红球个数严格大于蓝球
• 红球和蓝球个数相等，且最后一个球是蓝色的

设有$R$个红球，$B$个蓝球，考虑这种情况下有多少种不同的取球序列。

1. $R<B$：
   显然无论如何都不会使所有变色龙都变成红色，方案数为$0$。
2. $R=B$：
   符合条件的序列必定满足：

• 最后一个球为蓝球
• 存在$n$个不相交的$(红,蓝)$子序列

我们将其放入平面直角坐标系中，以红色球为$x$，蓝色球为$y$，那么最后一定要走到$(R,B-1)$，然后再取一个蓝球，走到$(R,B)$。满足第二个条件则需要使得不存在路径上的点满足$y-x\ge B-n+1$。这是因为不满足条件的情况一定是先取了很多蓝球，使得后面的蓝球不够匹配。由于最多有$B-n$个蓝球能不和红球匹配，这时蓝球个数和红球个数之差一定大于$B-n$，即一定有某个点满足$y\ge x+(B-n+1)$。
3. $R>B$:
符合条件的序列必定满足：

• 存在$\max(0,n-(R-B))$个不相交的$(红,蓝)$子序列

与前面的情况相同，类似地，序列个数等价于从$(0,0)$走到$(R,B)$且不经过$y\ge x+(R-n+1)$的点的路径条数。

接下来考虑如何解决形如“计算从$(0,0)$走到$(X,Y)$且不经过$y\ge x+T$的点的路径个数”的问题。
考虑对于一条非法路径，如何使其变为一条合法路径。如果这条路径第一次经过$y\ge x+T$的点在$(p,q)$处，将其后面走的路径反转，即向上变为向右，向右变为向上，那么最后一定会走到$(Y-T,X+T)$。因此非法路径与从$(0,0)$走到$(Y-T,X+T)$的路径一一对应。因此路径个数为$\binom{X+Y}{X}-\binom{X+Y}{X+T}$。
由此，将$T$变为$(B-n+1)$和$(R-n+1)$带入即可得到前面的路径种数。

综上，枚举和为$K$的$R,B$，对于每种情况计算其方案数相加即可。

Code

#include <bits/stdc++.h>
#define P 998244353
#define MAX_N 1000000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt fac[MAX_N+5], inv[MAX_N+5], ans;
void init(int n) {
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1]*i%P;
    for (int i = 2; i <= n; i++) inv[i] = (P-P/i*inv[P%i]%P)%P;
    for (int i = 2; i <= n; i++) inv[i] = inv[i-1]*inv[i]%P;
}
lnt C(int n, int m) {return n >= m ? fac[n]*inv[m]%P*inv[n-m]%P : 0;}
lnt calc(int X, int Y, int T) {
    if (Y-X >= T || T <= 0) return 0;
    return (C(X+Y, X)-C(X+Y, X+T)+P)%P;
}
int main() {
    int n, m; read(n), read(m), init(m<<1);
    for (int R = m, B = 0; R >= B; R--, B++)
        if (R ^ B) ans = (ans+calc(R, B, R-n+1))%P;
        else ans = (ans+calc(R, B-1, B-n+1))%P;
    return printf("%lld\n", ans), 0;
}