G - Yet Another RGB Sequence

数学不好的记录一下.

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

考虑先放$G,B,RGG,B,RG$,最后补$RR$.

考虑先放的方案数就是$(nu{m}_G+nu{m}_B)!\mathrm{/}(nu{m}_G-k)!\ast (nu{m}_B)!\ast (k)!(num\_G+num\_B)!/(num\_G-k)!*(num\_B)!*(k)!$.

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

再然后考虑补$RR$.$RR$不能放在$GG$的前面,我们可以做一个操作就是把含有$GG$的向最近的$B,RGB,RG$合并,然后呢,我们随便插入那些块就行了,$B+RGB+RG$的数量是$nu{m}_B+knum\_B+k$,插入的数量为$nu{m}_R-knum\_R-k$,那么隔板法一下就是$C(nu{m}_B+nu{m}_R,nu{m}_R-k)C(num\_B+num\_R,num\_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;
}