题解：AT_agc040_f [AGC040F] Two Pieces

· · 题解

组合意义神仙题……

看其他题解没看懂讲的是什么意思，所以自己写一篇 qwq。

前置知识：隔板法

有 n 个相同的球，放进 m 个不同的盒子里，要求每个盒子不为空，有多少种方法？

答案是 C_{n-1}^{m-1}。我们可以看做在 n 个球中间插入 m-1 个隔板，因为有 n-1 个空隙，选出 m-1 个，所以答案是 C_{n-1}^{m-1}。

有 n 个相同的球，放进 m 个不同的盒子里，有多少种方法？

答案是 C_{m+n-1}^{n}。可以先往每个盒子里放个“假球”，然后用第一类隔板法得到 C_{m+n-1}^{m-1}=C_{m+n-1}^{n}。（upd on 25.12.02）

本题做法

因为两个棋相同，所以不放设两个棋为 u,v，且 u \leq v。

考虑在移动 v 的操作中插入移动 u 的操作。

首先插入令 u 加上 1 的操作，假设有 i 个，我们枚举 i（考虑始终满足 u \neq v，把 u=v-1 的操作转为操作二）。根据插板法第一个例子可以知道是 C_{B+i-1}^{i}-C_{B+i-1}^{i-1}。

然后考虑插入令 u=v 的操作。注意到可以相邻。空位有 n-B-i 个。要插入 A-i 个，根据插板法第二个例子可以知道是 C_{n-B-i+A-i-1}^{A-i}=C_{n+A-B-2i-1}^{A-i}。

乘起来即可。但是有一个细节：若 i+B=n，当且仅当 i=A 时有贡献，贡献为 C_{B+i-1}^{i}-C_{B+i-1}^{i-1}。

最后是 i 的值域。显然是 \min\{A,\min\{B-1,n-B\}\}。

然后做就行了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n, a, b, fac[10000005], inv[10000005], ans;
int qpow(int x, int k){
    int ans = 1;
    while (k){
        if (k & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}
int qmod(int a, int b){
    return a * qpow(b, mod - 2) % mod;
}
int C(int n, int m){
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
int nmod(int x){
    return (x % mod + mod) % mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> a >> b;
    if (!a && !b){
        cout << 1;
        return 0;
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    for (int i = 0; i <= n; i++)
        inv[i] = qmod(1, fac[i]);
    for (int i = 0; i <= min(min(a, b - 1), n - b); i++){
        if (n - b - i == 0){
            if (i == a)
                ans = (ans + nmod(C(b + i - 1, i) - C(b + i - 1, i - 1))) % mod;
        }else{
            int qwq = (nmod(C(b + i - 1, i) - C(b + i - 1, i - 1))) % mod;
            ans = (ans + (qwq * C(n + a - b - 2 * i - 1, a - i) % mod)) % mod;
        }
    }
    cout << ans;
    return 0;
}