[ABC266G] Yet Another RGB Sequence题解

· · 题解

题解全是反演？我来一发组合意义的题解吧。

首先我们考虑把 \texttt{rg} 算成字符 \texttt{\#}。

题面即变为：求 R - k 个 \texttt{r}，G-k 个 \texttt{g}，B 个 \texttt{b}，k 个 \texttt{\#} 组成不含 \texttt{rg} 的序列的方案数。

此时，我们先把 \texttt{g},\texttt{b} 和 \texttt{\#} 排好，方案即为 C_{G-k +B+k}^{G-k} \times C_{B+k}^k。

再考虑把 R-k 个 \texttt{r} 加入，此时不能将 \texttt{r} 放在 \texttt{g} 前面，所以这一步有 C_{R-k+B+k}^{R-k} 种方案。

故共有 C_{G+B}^{G-k} \times C_{B+k}^k \times C_{R+B}^{R-k} 种方案。

贴一下代码（本人在实现中先将 R 和 G 减去了 k ，但化简后与文字叙述中的式子相同）：

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int a,b,c,d,ans;
int ksm(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y%2) ret*=x,ret%=mod;
        x*=x,x%=mod,y/=2;
    }
    return ret;
}
int C(int n,int m)
{
    if(m>n/2) m=n-m;
    if(m==0) return 1;
    int ret=1;
    for(int i=n;i>=n-m+1;i--)
        ret*=i,ret%=mod;
    for(int j=1;j<=m;j++)
        ret*=ksm(j,mod-2),ret%=mod;
    return ret;
}
signed main()
{
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    a-=d,b-=d;
    ans=C(c+d+b,b)*C(d+c,d)%mod*C(c+d+a,a)%mod;
    printf("%lld",ans);
    return 0;
}