2021牛客多校第四场G (容斥,组合计数) G-Product_2021牛客暑期多校训练营4 (nowcoder.com)
思路:
先证一个公式
\(\sum_{a_i\ge0,\sum a_i=D}\prod \frac{1}{a_i!}=\frac{n^D}{D!}\)
考虑一个组合数学问题,有D个球,n种颜色,每种颜色的球有 \(a_i\) 个
那么,当每个 \(a_i\) 都确定时,这种情况下的方案数为\(\frac{D!}{\prod a_i!}\)
而所有放颜色的方案数显然为\(n^D\)
那么就有 \(\sum_{a_i>=0,\sum a_i=D}\prod \frac{D!}{a_i!}=n^D\)
两边同时除以 \(D!\) 即得上式
原题目要我们求的式子可化为\(D!\sum_{a_i\ge k,\sum a_i=D+nk}\prod \frac{1}{a_i!}\)
如果说没有\(a_i\ge k\)的限制,那么我们要求的答案就是\(D!\frac{n^{D+nk}}{(D+nk)!}\)
所以我们要将所有 \(a_i<k\)的情况容斥掉
设事件 \(A_i\) 表示\(a_i<k\)
那么所有不合法的情况即为
\(|A_1\bigcup A_2\bigcup\cdots\bigcup A_{n-1}\bigcup A_n|=\\\sum_{1\le i\le m}|A_i|-\sum_{1\le i<j\le m}|A_i\bigcap A_j|+\cdots+(-1)^{n-1}|A_1\bigcap A_2\bigcap\cdots\bigcap A_n|\)
令 \(dp[i][j]\) 表示 \(j\) 个球分到 \(i\) 个非法组的情况,枚举最后一个非法组的球数和 \(j\) 个球的分配情况
\(dp[i][j]=\sum_{t=0}^{k-1}dp[i-1][j-t]\left(\matrix{j\\t}\right)\)
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,k,D;
const int maxn=55;
int c[maxn*maxn][maxn*maxn];
int dp[maxn][maxn*maxn];
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
void init()
{
c[0][0]=1;
for(int i=1;i<=n*k;i++)
for(int j=1;j<=i;j++)
{
c[i][0]=1;
c[i][j]=c[i-1][j-1]+c[i-1][j];
if(c[i][j]>=mod)c[i][j]-=mod;
}
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i*(k-1);j++)
{
for(int v=0;v<=j&&v<k;v++)
{
// cout<<i<<" "<<j<<" "<<v<<"\n";
dp[i][j]=(dp[i][j]+1ll*dp[i-1][j-v]*c[j][v]%mod)%mod;
}
}
}
}
int main()
{
cin>>n>>k>>D;
init();
long long ans=ksm(n,D+n*k);
for(int i=1;i<=n;i++)
{
int sgn,mul;
if(i&1)sgn=mod-1;
else sgn=1;
mul=1;
for(int j=0;j<=i*(k-1);j++)
{
ans=(ans+1ll*sgn*c[n][i]%mod*ksm(n-i,D+n*k-j)%mod*dp[i][j]%mod*mul%mod)%mod;
mul=1ll*mul*(D+n*k-j)%mod*ksm(j+1,mod-2)%mod;
}
}
for(int i=D+1;i<=D+n*k;i++)
{
ans=1ll*ans*ksm(i,mod-2)%mod;
}
printf("%lld\n",ans);
return 0;
}
另一种生成函数的思路,参考【题解】2021牛客暑期多校第四场 G.Product - bobh - 博客园 (cnblogs.com)
由于\(e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}\)
所以\(\sum_{a_i>=0,\sum a_i=D}\prod \frac{1}{a_i!}=[x^D](e^x)^n\)
设\(b_i=a_i+k\)
原题转化为求\(\sum_{b_i>=k,\sum b_i=D+nk}\prod \frac{D!}{b_i!}\)
由于\(b_i\ge k\)要去除小于k的项
即要求解\([x^{D+nk}](e^x-\sum_{i=0}^{k-1}\frac{x^i}{i!})^n\)
计 \(A(x)=-\sum_{i=0}^{k-1}\frac{x^i}{i!}\),预处理\(A(x),A^2(x),\cdots,A^n(x)\)
暴力展开\((e^x+A(x))^n=\sum_{i=0}^n\left(\matrix{n\\i}\right)A^ie^{(n-i)x}\)