「联合省选 2020 A」组合数问题

题意：

求$\begin{aligned}\sum _{k=0}^nf(k)\cdot x^k\cdot C(n,k)\end{aligned}$

显然要对于$f(k)$的每一项考虑，第$i$项的贡献

$a_i\begin{aligned}\sum _{k=0}^nk^i\cdot x^k\cdot C(n,k)\end{aligned}$

通用的$O(m^2)$

后面的这个式子，考虑它的组合意义，假设当前有$n$个格子，每个格子被染了$[0,x]$的颜色

$x^k\cdot C(n,k)$即枚举有$k$个格子涂了$[1,x]$的颜色，剩下涂了$0$的颜色

$k^i$的组合意义即可重复地选了$i$次，每次选出的都是在$[1,x]$颜色的格子的方案数

那么问题可以转化为强制每一次被访问的格子都是$[1,x]$，其他的格子随便涂$[0,x]$

问题在于每次被访问的格子会重复，于是可以想到一个简单的转化，求出$i$次访问了$j$不同位置的方案数

即斯特林数$S(i,j)$，可以得到的是

$\begin{aligned}\sum _{k=0}^nk^i\cdot x^k\cdot C(n,k)=\sum_{j=0}^iS(i,j)\cdot \frac{n!} {(n-j)!}\cdot x^j(x+1)^{n-j}\end{aligned}$

实际上可以在$O(m^2)$递推斯特林数时就把$\frac{n!} {(n-j)!}$加入权值，$x^j(x+1)^{n-j}$可以预处理出来

因此总复杂度就是$O(m^2)$

#include<cstdio>
long long i,j,n,m,P,x,y,F[1010],Pow[1010],r,ans;
int qpow(int x,int k) { 
	for(r=1;k;k>>=1,x=1ll*x*x%P) if(k&1) r=r*x%P; 
	return r; 
}
int main(){
	freopen("problem.in","r",stdin),freopen("problem.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld",&n,&x,&P,&m,&y),F[0]=1,ans=qpow(x+1,n)*y%P;
	for(int i=0;i<=m;++i) Pow[i]=1ll*qpow(x,i)*qpow(x+1,n-i)%P;
	for(i=1;i<=m;++i) {
		long long res=0;
		for(j=i,scanf("%lld",&y);~j;--j) {
			F[j]=(F[j]*j+(j?F[j-1]*(n-j+1):0))%P; // 类似斯特林数的递推
			res=(res+F[j]*Pow[j])%P;
		}
		ans=(ans+res*y)%P;
	}
	printf("%lld",ans);
}

特殊的$O(m\log^2 m)$

(注意以下仅限于口胡!)

假设可以把$f(k)$转化为下降幂多项式，依然枚举每一项考虑，那么每次要求的就是

$\begin{aligned}\sum _{k=0}^nk^{\underline i}\cdot x^k\cdot C(n,k)=i!\sum _{k=0}^nC(k,i)\cdot x^k\cdot C(n,k)\end{aligned}$

依然考虑组合意义

$x^k\cdot C(n,k)$即枚举有$k$个格子涂了$[1,x]$的颜色，剩下涂了$0$的颜色

$C(k,i)$的组合意义不可重复地选了$i$次，每次选出的都是在$[1,x]$颜色的格子的方案数

那么问题可以转化为强制每一次被访问的格子都是$[1,x]$，其他的格子随便涂$[0,x]$

$\begin{aligned}\sum _{k=0}^nk^{\underline i}\cdot x^k\cdot C(n,k)=i!\cdot C(n,i)\cdot x^i\cdot (x+1)^{n-i}\end{aligned}$

(式子应该没有问题，但是下面都是口胡)

求解下降幂多项式需要多点求值，还要求很多逆元

然而对于非质数的$P$，我们求不出$i!$的逆元

(比较智障的搞法就是每次乘法都存下$P$的每个质因数个数，这样，做乘法的复杂度是$\log P$，但是不知道最后做出的答案是不是能保证因数个数$\ge 0$)

对于$P$为质数的情况，用$\text{MTT}$做多项式转下降幂多项式的复杂度是$O(m\log^2 m)$

(听说用转置原理优化的多点求值已经可以跑$10^6$啦?)