Yet Another RGB Sequence（排列组合）

题意

问有多少字符串满足如下要求：

• 只包含R、G、B三种字符，并且数量分别是\(A\)，\(B\)，\(C\)。
• 包含\(K\)个连续子串RG。

题目链接：https://atcoder.jp/contests/abc266/tasks/abc266_g

数据范围

\(1 \leq A,B,C \leq 10^6\)

思路

我们将题目转化一下，有\(A+B+C\)个位置上要放R、G、B三种字符。其中RG有\(K\)个，R有\(A-K\)个，G有\(B-K\)个，B有\(C\)个。

我们可以将RG当做是一个字符，因此唯一的限制就在于除了RG之外的其他R和G。

因此，我们可以将RG、R和B随便放，方案数是\(\frac{(K + (A - K) + C)!}{K!(A-K)!C!}\)。

然后考虑放G。本来有\(K + (A - K) + C + 1\)个位置，但是由于不能放在R的后面，因此实际可以放的位置为\(K + C + 1\)个。

这样就转化成了一个不定方程解的个数问题，方案数为\(\binom{(B-K) + (K + C + 1) - 1}{(K +C+1)-1} = \binom{B+C}{C+K}\)

因此最终结果为\(\frac{(A + C)!}{K!(A-K)!C!} \cdot \binom{B+C}{C+K}\)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 2000010, mod = 998244353;

ll a, b, c, k;
ll fac[N], infac[N];

ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

void init()
{
    fac[0] = infac[0] = 1;
    for(int i = 1; i < N; i ++) {
        fac[i] = fac[i - 1] * i % mod;
        infac[i] = infac[i - 1] * qmi(i, mod - 2) % mod;
    }
}

int main()
{
    cin >> a >> b >> c >> k;
    init();
    ll res = fac[a + c] * infac[a - k] % mod * infac[c] % mod * infac[k] % mod;
    res = res * fac[b + c] % mod * infac[c + k] % mod * infac[b - k] % mod;
    cout << res << endl;
    return 0;
}