网站怎么做付款平台/汕头seo外包机构

LINK

一个序列$a$的权值定义为$\frac{D!}{{\prod }_{i=1}^n(a_i+k)!}$

合法的序列$a$满足$\sum _{i=1}^n{a}_i=D$且$a_i>=0$

求所有合法序列的权值和模$998244353$

其中$D<=10^8,n<=50,k<=50$

---

考虑先求

$ans1=\sum _{a_i>=0\&\&(\sum _{i=1}^n{a}_i)=D}\frac{D!}{\prod _{i=1}^n{a}_{i!}}$

考虑$D!\ast \prod _{i=1}^n\frac{1}{a_i!}$的意义

相当于一个可重集排列问题,$D$个小球排成一排,第$i$种小球有$a_i$个,求排列的方案数

考虑现在$a_i$的值不是固定的,相当于求一个给$D$个小球分配颜色并排列的方案,这显然有更简单的算法

考虑拿出的第$i$个小球排列在第$i$个位置,那么它的颜色可以有$n$种,总方案也就是$n^D$

于是我们知道$ans1=n^D$

不过题目要求的是

$ans2=\sum _{a_i>=0\&\&(\sum _{i=1}^n{a}_i)=D}\frac{D!}{\prod _{i=1}^n(a_i+k)!}$

这样就用不了上面的结论了,考虑变形一下来使用上面的结论

$ans2=\sum _{a_i>=k\&\&(\sum _{i=1}^n{a}_i)=D+nk}\frac{D!}{\prod _{i=1}^n{a}_i!}=\frac{D!}{(D+nk)!}\ast n^{D+nk}$

这样肯定算多了,因为在这$n$种颜色中,很多颜色没有分配够$k$,有些颜色分配够了

这个需要容斥掉不合法的方案数,不妨定义$f[i][j]$表示$i$个位置不合法,这些数字的和是$j$共造成的贡献

$f[i][j]=f[i-1][j-q]\ast \frac{1}{q!}$

显然有$\left(\genfrac{}{}{0ex}{}{n}{i}\right)$种取法,不满足的位置贡献是$f[i][j]$

满足的位置按照上面的计算方式有$\frac{D!}{(D+nk-j)!}(n-i{)}^{D+nk-j}$的贡献,乘起来就好了

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6+10;
const int mod = 998244353;
int n,k,D,a[maxn],fac[maxn],inv[maxn];
int f[2509][2509],C[2509][2509];
int quick(int x,int n)
{int ans = 1;for( ; n ; n>>=1,x=x*x%mod )if( n&1 )	ans = ans*x%mod;return ans; 
}
void upd(int &x,int y){ x = (x+y)%mod; }
void init()
{fac[0] = 1;for(int i=1;i<=k;i++)	fac[i] = fac[i-1]*i%mod;for(int i=k;i>=0;i--) inv[i] = quick( fac[i],mod-2 );for(int i=0;i<=n*k;i++){C[i][0] = 1;for(int j=1;j<=i;j++)C[i][j] = ( C[i-1][j-1]+C[i-1][j] )%mod;}	 f[0][0] = 1;//有i个<k且和为jfor(int i=1;i<=n;i++)for(int j=0;j<=n*k;j++)for(int q=0;q<k && q<=j;q++)upd( f[i][j],f[i-1][j-q]*inv[q]%mod );
}
int get(int l,int r)
{int ans = 1;for(int i=l+1;i<=r;i++)	ans = ans*i%mod;return quick( ans,mod-2 );
}
signed main()
{cin >> n >> k >> D;init();int ans = 0;for(int i=0;i<=n;i++)for(int j=0;j<=n*k;j++){int fu = (i&1)?-1:1, sum = D+n*k-j;upd( ans,fu*C[n][i]*f[i][j]%mod*get(D,sum)%mod*quick(n-i,sum)%mod );}cout << ( ans%mod+mod )%mod;
}