[C++知识库]AT3871 [AGC021E] Ball Eat Chameleons

https://www.luogu.com.cn/problem/AT3871

建议先做[SCOI2010]生成字符串

好了直接来分析这一题

假设红蓝球数为$R,B$
$R+B=k$
首先一定要满足$R\ge B$
如果$R\ge B+n$显然随便拍就行，容易计算$\left(\genfrac{}{}{0ex}{}{R+B}{R}\right)$

如果$R<B+n$ 必定是每个变色龙先吃红，再吃蓝，再吃红交替

刚好有$R?B$个变色龙红的比蓝的多一个，这些变色龙就不用管了（最后多吃一个$R$就掰回去了），主要看剩下红蓝相等的

有$n?(R?B)$个

也就是至少要有这么多个蓝球要在红球后面

那么相当于最多只能有$B?(n?(R?B))=R?n$个蓝球在红球前面（没有被匹配）

把红球看成$+1$,蓝球看成$?1$,就是这个序列任意的前缀和要$>=?(R?n)$

相当于是不碰线的路径计数问题

这是个经典问题，和上面那题一样

从原点出发，$+1$表示往右上方走一格子$(x+1,y+1)$，$?1$表示往右下走一格子$(x?1,y?1)$
然后不能碰到$y=?(R?n)?1$这条线
求方案数

只需要在第一次碰线的时候把前面那一段关于那条线对称一下

发现有$R?n+1$个右下的变成右上的了，其他不变，于是用总的减去这些就行了

$$\left(\genfrac{}{}{0ex}{}{R+B}{R}\right)?\left(\genfrac{}{}{0ex}{}{R+B}{R+(R?n+1)}\right)$$

还有一种特殊情况，当$R=B$的时候，因为你多的蓝球没地方扔，不对，可以考虑先拿出来
一个蓝球（应为最后一个放的肯定是蓝球），然后就变得和上面那个问题一样了

code:

#include<bits/stdc++.h>
#define N 5000050
#define ll long long
#define mod 998244353
using namespace std;
ll qpow(ll x, ll y) {
    ll ret = 1;
    for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
    return ret;
}
ll fac[N], ifac[N];
int n, k;
void init(int n) {
    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 >= 0; i --) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
ll C(int n, int m) {
    if(n < m || m < 0 || n < 0) return 0;
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main() {
    scanf("%d%d", &n, &k); init(max(n, k));
    if(k < n) {
        printf("0");
        return 0;
    }
    ll ans = 0;
    for(int r = 0; r <= k; r ++) {
        int b = k - r;
        if(r < b) continue;
        if(r == b) b --;
        ans = (ans + C(r + b, r)) % mod;
        if(r < n + b) ans = (ans - C(r + b, r + r - n + 1) + mod) % mod;
    }
    printf("%lld", ans);
    return 0;
}