补题情况

题目	蒋贤蒙	王智彪
A	0	0
B	2	2
C	2	1
D	0	0
E	2	1
F	2	2
G	0	0
H	0	0
I	2	2
J	2	2

题解

G. Product

题意

给定 $n,k,D$，求

$$ \sum_{\sum a_i=D,a_i\ge 0}\frac {D!}{\prod_{i=1}^n (a_i+k)} $$

题解

不妨设 $b_i=a_i+k$

$$ \sum_{\sum a_i=D,a_i\ge 0}\frac {D!}{\prod_{i=1}^n (a_i+k)}=\frac {D!}{(D+nk)!}\sum_{\sum b_i=D+nk,b_i\ge k}\frac {(D+nk)!}{\prod_{i=1}^n b_i} $$

不难发现，式子右半部分的组合意义是由元素 $1\sim n$ 构成的长度为 $D+nk$ 的排列个数，其中每个元素出现次数不小于 $k$。

不妨考虑容斥，设 $\text{dp}(i,j)$ 表示由元素 $1\sim i$ 构成的长度为 $j$ 的排列个数，其中每个元素出现次数小于 $k$，不难得到状态转移

$$ \text{dp}(i,j)=\sum_{v=0}^{\min(j,k)}{j\choose v}\text{dp}(i-1,j-v) $$

同时有公式 $n$ 种元素出现次数无限制时构成的长度为 $k$ 的排列个数为 $n^k$，于是有

$$ \sum_{\sum b_i=D+nk,b_i\ge k}\frac {(D+nk)!}{\prod_{i=1}^n b_i}=\sum_{i=0}^n (-1)^n\sum_{j=0}^{ik}{D+nk\choose j}\text{dp}(i,j)(n-i)^{D+nk-j} $$

总时间复杂度 $O\left(n^2k^2\right)$。

查看代码

const int MAXN=55,MAXV=MAXN*MAXN,mod=998244353;
int quick_pow(int a,int k){
	int ans=1;
	while(k){
		if(k&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		k>>=1;
	}
	return ans;
}
int frac[MAXV],invf[MAXV],down[MAXV];
int C(int n,int m){
	return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
}
int C2(int n){
	return 1LL*down[n]*invf[n]%mod;
}
int dp[MAXN][MAXV];
int main(){
	int n=read_int(),k=read_int(),D=read_int();
	//pre
	frac[0]=1;
	_for(i,1,MAXV)frac[i]=1LL*frac[i-1]*i%mod;
	invf[MAXV-1]=quick_pow(frac[MAXV-1],mod-2);
	for(int i=MAXV-1;i;i--)
	invf[i-1]=1LL*invf[i]*i%mod;
	down[0]=1;
	_for(i,0,n*k)
	down[i+1]=1LL*down[i]*(D+n*k-i)%mod;
	//main
	LL ans=quick_pow(n,D+n*k);
	dp[0][0]=1;
	_rep(i,1,n){
		_for(j,0,i*k){
			_for(v,0,k){
				if(j>=v)
				dp[i][j]=(dp[i][j]+1LL*dp[i-1][j-v]*C(j,v))%mod;
			}
			int d=1LL*dp[i][j]*C(n,i)%mod*C2(j)%mod*quick_pow(n-i,D+n*k-j)%mod;
			if(i&1)
			ans=(ans+mod-d)%mod;
			else
			ans=(ans+d)%mod;
		}
	}
	int t=1;
	_rep(i,D+1,D+n*k)
	t=1LL*t*i%mod;
	ans=ans*quick_pow(t,mod-2)%mod;
	enter(ans);
	return 0;
}

CVBB ACM Team

目录

补题情况

题解

G. Product

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

补题情况

题解

G. Product

题意

题解

页面工具