ABC266G解题报告

· · 题解

题意

求符合要求的字符串个数，对 998244353 取余。

满足要求的字符串 s 具备以下特性：

分析

很明显发现是一道排列组合的题，恰好本蒟蒻刚学了卢卡斯定理。

开始推式子，我们发现 r 和 g 的排列会影响到 rg 的个数，不妨先把 r 提出来，先去算剩下有多少种排列，再把 r 加进去计算总排列数。而 rg 中包含了一个 r 和一个 g，所以之后排列的 r 和 g 的个数为 R-k 和 G - k。

至于式子，考虑简化版的，只有 r，g，b 的限制，那么 r 就有 C_{R+G+B}^R \times C_{G+B}^{G} 种情况（先填 r 后填 g 最后 b 的位置也就确定了，R+G+B 表示字符串总长度）。那么原题中把 r 提出来后同理有 C_{G-k+B+k}^{G-k} \times C_{B+k}^k 种情况。

再考虑加了 r 之后的情况，因为前面的操作使得我们不能在之后的操作中形成 rg，所以之后 r 能选择的位置就只剩下了总数减去 r 的个数。

最后得到式子 C_{G-k+B+k}^{G-k} \times C_{B+k}^k \times C_{R-k+B+k}^{R-k}=C_{G+B}^{G-k} \times C_{B+k}^k \times C_{R+B}^{R-k}。

很明显这题不能暴力求组合数，必须通过卢卡斯定理，不会的自行百度。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 998244353;
int r, g, b, k;

int ksm(int a, int b, int p){
    int res = 1;
    while (b){
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int C(int a, int b, int p){
    if (b > a) return 0;
    int res = 1;
    for (int i = a, j = 1; j <= b; i--, j++){
        res = res * i % p;
        res = res * ksm(j, p - 2, p) % p;
    }
    return res;
}

int lucas(int a, int b, int p){
    if (a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; 
}

signed main(){
    cin >> r >> g >> b >> k;
    cout << lucas(g + b, g - k, mod) * lucas(b + k, k, mod) % mod * lucas(r + b, r - k, mod) % mod << endl;//lucas套公式
    return 0;
}