G - Yet Another RGB Sequence

数学不好的记录一下.

题目是给定 $R, G, B$ 的数量.然后给你一个 $k$ ,要求字符串中有 $k$ 个 $R G$ 的方案数.

考虑先放 $G, B, R G$ ,最后补 $R$ .

考虑先放的方案数就是 $(n u m_{G} + n u m_{B})! / (n u m_{G} - k)! * (n u m_{B})! * (k)!$ .

多重集的排列,总的方案/内部随便排的方案数.

再然后考虑补 $R$ . $R$ 不能放在 $G$ 的前面,我们可以做一个操作就是把含有 $G$ 的向最近的 $B, R G$ 合并,然后呢,我们随便插入那些块就行了, $B + R G$ 的数量是 $n u m_{B} + k$ ,插入的数量为 $n u m_{R} - k$ ,那么隔板法一下就是 $C (n u m_{B} + n u m_{R}, n u m_{R} - k)$ .

然后两个方案数相乘就是答案了.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=3e6+5;
const int M=7;
const int mod=998244353;
const double pi=acos(-1);

int f[N],ivf[N];

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

int C(int a,int b)
{
	return 1ll*f[a]*ivf[a-b]%mod*ivf[b]%mod;
}

void run()
{
	int r,g,b,k;
	cin>>r>>g>>b>>k;
	int n=3e6;
	f[0]=1;
	for(int i=1;i<=n;i++)
		f[i]=1ll*f[i-1]*i%mod;
	ivf[n]=qp(f[n],mod-2);
	for(int i=n-1;i>=0;i--)
		ivf[i]=1ll*ivf[i+1]*(i+1)%mod;
	ll ans=1ll*f[g+b]*ivf[g-k]%mod*ivf[b]%mod*ivf[k]%mod;
	ans=ans*C(b+r,r-k)%mod;
	cout<<ans<<'\n';	
}

int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	run();
	return 0;
}