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

#「联合省选 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\) 啦?)