嘘~ 正在从服务器偷取页面 . . .

[ABC266G] Yet Another RGB Sequence 题解

发布日期: 2023-06-03

更新日期: 2023-06-05

文章字数: 549

[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;
}