读题后立马想到容斥:嗯先算由 \(R-K,G-K,B,0\) 构成的方案数,再把 \(K\) 个 RG 插入。这样就 完美 地简化成模型了!
但明显把 \(K\) 个 RG 删掉后剩下的序列可能会合并出新的 RG 。。。
Notice:考虑方案数是否一样需要插入,也要删除。即要证明充分必要性!
于是枚举 \(i\in [0,min(R-K,G-K)]\),计算 RG 数大于等于 \(K+i\) 个的方案数。
这里提供一个可以用来配系数,同时也是证明正确性的方法:
设有恰好 \(K+j\) 个 RG 的方案数为 \(X\),我们在某个 \(i\) 时计算的值包含有 \(C_{K+j}^{K+i}\) 个 \(X\),明显系数不对。
考虑之前的证明时运用 \(\sum_{i=0}^{i<=j} (-1)^i\times C_{j}^{i}\) 的特殊性,那么同样,我们的目标是凑出一个 常系数 \(\times C_{j}^{i}\)。又明显总数确定为 \(K+j\) 了,于是可以得出正确的系数应该为
\[C_{K+j}^{j}\times C_{j}^{i} \]那么再运用组合基本知识(其实就是取反+改变枚举顺序),变形为
\[C_{k+j}^{K+i}\times C_{K+i}^{i} \]于是我们就找到了应该补上的系数 \(C_{K+i}^{K}\)
当然,感性理解的话就是 \(K\) 个 RG 和剩余 \(i\) 个 RG 并不完全一样,需要再次计算。
#include<bits/stdc++.h>
using namespace std;
#define N 3000006
const int mod=998244353;
int jc[N],jcinv[N],fu[N];
int power(int x,int c){
int now=1;
while(c){
if(c&1)now=1ll*now*x%mod;
x=1ll*x*x%mod;c>>=1;
}
return now;
}
inline void init(int n){
jc[0]=1;
for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%mod;
fu[0]=1;
for(int i=1;i<=n;++i)fu[i]=fu[i-1]*(-1);
jcinv[n]=power(jc[n],mod-2);
for(int i=n-1;i>=0;--i)jcinv[i]=1ll*jcinv[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int ans[N];
int main(){
init(N-1);
int R,G,B,K;cin>>R>>G>>B>>K;
int ans=0;R-=K;G-=K;
for(int i=0;i<=min(R,G);++i){
ans=(ans+1ll*power(-1,i)*C(R+G-i-i,G-i)%mod*C(R+G-i-i+B,B)%mod*C(R+G-i+B+K,i+K)%mod*C(K+i,i)%mod)%mod;
}
ans=(ans+mod)%mod;
cout<<ans<<endl;
return 0;
}
当然,若是不用容斥,也可以直接计算。
容易发现,其实随意排列时只需要满足 R 和 G 不连续就好了。
假设是 G 插入含 R 的序列,那么只要把所有 R 跟它下一位合并,捆绑在一起排列,就不会出现 RG 了。
#include<bits/stdc++.h>
using namespace std;
#define N 3000006
const int mod=998244353;
int jc[N],jcinv[N],fu[N];
int power(int x,int c){
int now=1;
while(c){
if(c&1)now=1ll*now*x%mod;
x=1ll*x*x%mod;c>>=1;
}
return now;
}
inline void init(int n){
jc[0]=1;
for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%mod;
fu[0]=1;
for(int i=1;i<=n;++i)fu[i]=fu[i-1]*(-1);
jcinv[n]=power(jc[n],mod-2);
for(int i=n-1;i>=0;--i)jcinv[i]=1ll*jcinv[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
return 1ll*jc[n]*jcinv[m]%mod*jcinv[n-m]%mod;
}
int ans[N];
int main(){
init(N-1);
int R,G,B,K;cin>>R>>G>>B>>K;
int ans=0;R-=K;G-=K;
ans=1ll*C(R+B,R)*C(R+B+K,K)%mod*C(G+B+K,G)%mod;
ans=(ans+mod)%mod;
cout<<ans<<endl;
return 0;
}
标签:int,1ll,jcinv,RGB,RG,Another,now,Yet,mod
From: https://www.cnblogs.com/Huster-ZHY/p/16789147.html