洛谷 P2791 - 幼儿园篮球题（第二类斯特林数）

题面传送门

首先写出式子：

\[ans=\sum\limits_{i=0}^m\dbinom{m}{i}\dbinom{n-m}{k-i}·i^L \]

看到后面有个幂，我们看它不爽，因此考虑将其拆开，具体来说，根据普通幂转下降幂的式子：

\[i^L=\sum\limits_{j=1}^L\begin{Bmatrix}L\\j\end{Bmatrix}\dbinom{i}{j}·j! \]

我们可以得到

\[ans=\sum\limits_{i=0}^m\dbinom{m}{i}\dbinom{n-m}{k-i}\sum\limits_{j=1}^L\begin{Bmatrix}L\\j\end{Bmatrix}\dbinom{i}{j}·j! \]

交换求和号

\[ans=\sum\limits_{j=1}^L\begin{Bmatrix}L\\j\end{Bmatrix}\sum\limits_{i=0}^m\dbinom{m}{i}\dbinom{n-m}{k-i}\dbinom{i}{j} \]

调用吸收恒等式把 \(\dbinom{m}{i}\dbinom{i}{j}\) 化简开来可以得到

\[\dbinom{m}{i}\dbinom{i}{j}=\dbinom{m}{j}\dbinom{m-j}{i-j} \]

代入原式

\[ans=\sum\limits_{j=1}^L\begin{Bmatrix}L\\j\end{Bmatrix}\sum\limits_{i=0}^m\dbinom{m}{j}\dbinom{m-j}{i-j}\dbinom{n-m}{k-i} \]

调用范德蒙德卷积化简 \(\sum\limits_{i=0}^m\dbinom{m-j}{i-j}\dbinom{n-m}{k-i}\)? 可得：

\[ans=\sum\limits_{j=1}^L\begin{Bmatrix}L\\j\end{Bmatrix}\dbinom{m}{j}\dbinom{n-j}{k-j} \]

注意到这题 \(L\) 数据范围不大，因此可以 NTT 预处理处 \(\begin{Bmatrix}L\\j\end{Bmatrix}\)，这样可以 \(\mathcal O(N+L\log L+SL)\) 求解原问题。

注意常数问题，建议把组合数全部拆开来约分，这样可以有效地减少常数。

const int pr=3;
const int ipr=332748118;
const int MOD=998244353;
const int MAXN=2e7;
const int MAXP=1<<19;
int qpow(int x,int e){
	int ret=1;
	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
	return ret;
}
int fac[MAXN+5],ifac[MAXN+5];
void init_fac(int n){
	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int binom(int n,int k){
	if(n<0||k<0||n &a,int len,int type){
	int lg=31-__builtin_clz(len);
	for(int i=0;i>1]>>1)|((i&1)<>1);k++,w=1ll*w*W%MOD){
				int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
				a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
			}
		}
	}
	if(type==-1){
		int ivn=qpow(len,MOD-2);
		for(int i=0;i conv(vector a,vector b){
	int LEN=1;while(LEN a(l+1),b(l+1);
	for(int i=1;i<=l;i++) a[i]=1ll*qpow(i,l)*ifac[i]%MOD;
	for(int i=0;i<=l;i++) b[i]=(i&1)?(MOD-ifac[i]):ifac[i];
	vector c=conv(a,b);
//	for(int i=1;i<=l;i++) printf("%d\n",c[i]);
	while(s--){
		int n,m,k;scanf("%d%d%d",&n,&m,&k);int res=0;
		for(int i=1;i<=min(l,min(m,k));i++) res=(res+1ll*c[i]*fac[n-i]%MOD*ifac[m-i]%MOD*ifac[k-i])%MOD;
		printf("%d\n",1ll*res*fac[m]%MOD*ifac[n-k]%MOD*qpow(binom(n,k),MOD-2)%MOD);
	}
	return 0;
}