[ABC266G] Yet Another RGB Sequence 题解

题目链接：[ABC266G] Yet Another RGB Sequence

题意：

给定整数 \(R, G, B\) 和 \(K\)。

求有多少个由 \(\tt{R}\)、\(\tt{G}\) 和 \(\tt{B}\) 组成的字符串 \(S\) 满足以下所有条件？计算结果取模 \(998244353\) 。

• 字符串 \(S\) 中 \(\tt{R}\)、\(\tt{G}\) 和 \(\tt{B}\) 的出现次数分别为 \(R, G\) 和 \(B\)。
• 字符串 \(S\) 中连续出现的子字符串 \(\tt{RG}\) 的个数为 \(K\)。

数据范围：

\(1 \leq R, G, B \leq 10^6,~0 \leq K \leq \min (R, G)\) 。

一道有意思的计数题。记 \(\mathtt{rg}\) 为 \(🤡\) 。

则原题转化为求 \(R-k\) 个 \(\mathtt{r},~ G-k\) 个 \(\mathtt{g}, ~B\) 个 \(\mathtt{b}\) 和 \(k\) 个 \(🤡\) 组成不含 \(\mathtt{rg}\) 的序列的方案数。

因为此时 \(\tt{r}\) 和 \(\tt{g}\) 不能组成 \(\tt{rg}\) ，所以我们考虑先把 \(\mathtt{g},\mathtt{b},🤡\) 排好，方案数为 \[ \binom{G-k+B+k}{G-k}\times \binom{B+k}{k} \] 然后考虑把 \(R-k\) 个 \(\tt{r}\) 插入，注意此时不能把 \(\mathtt{r}\) 放到 \(\mathtt{g}\) 前面，则方案数为 \[ \binom{R-k+B+k}{R-k} \] 最后乘起来就好了。这里其实是把 \(🤡\) 当成了分隔符，钦定 \(\tt{r}\) 在前 \(\tt{g}\) 在后，这样不会出现 \(\tt{rg}\) 。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e6 + 15))

const int mod = 998244353;
int fac[N],inv[N];
int qpow(int a,int b,int c = 1)
{
    for(; b; b >>= 1) {
        if(b & 1) { c = c * a % mod; } a = a * a % mod;
    } return c;
}
void init(int n)
{
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for(int i = n; i; i--) inv[i - 1] = i * inv[i] % mod;
}
int C(int n,int m)
{
    if(n < m) return 0;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int a,b,c,d; cin >> a >> b >> c >> d; a -= d; b -= d; init(a+b+c+d);
    cout << C(c + d + b, b) * C(d + c, d) % mod * C(c + d + a, a) % mod << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/516369/solution-at-abc266-g