【题解】 「联合省选2020」组合数问题 第二类斯特林数+组合数学 LOJ3300

Link to LOJ

Legend

给定 \(n,x,p,m,a_i\),求:

\[\left(\sum\limits_{k=0}^{n}f(k)\times x^k \times \dbinom{n}{k} \right) \bmod p \]

保证 \(1 \le n,x,p \le 10^9\)\(0 \le a_i \le 10^9\)\(0 \le m \le \min(1000 ,n)\)

时空 \(\textrm{1s/512MB}\)

Editorial

作为 联合省选2020 的第二题,居然还是一道良心送温暖题,但至少区分掉了我,让我们一起为出题人点赞。

just Stirling

\[\begin{aligned} & \sum\limits_{k=0}^{n}f(k)\times x^k \times \dbinom{n}{k} \\ =& \sum_{k=0}^{n}\left(\sum_{i=0}^{m} a_ik^i\right) x^k\dbinom{n}{k} & 把多项式打开\\ =& \sum_{k=0}^{n}\left(\sum_{i=0}^{m} a_i\sum_{j=0}^{k}\begin{Bmatrix} i \\ j\end{Bmatrix}\dbinom{k}{j}j! \right) x^k\dbinom{n}{k} & 把 k^i 用第二类斯特林数打开\\ =& \sum_{k=0}^{n}\left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix}j! \right) x^k\dbinom{n}{k}\dbinom{k}{j} & 更改枚举上界+移项\\ =& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \right) \sum_{k=0}^{n} x^k\dbinom{n}{j}\dbinom{n-j}{k-j} j! & 组合意义化简\\ =& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \dbinom{n}{j}\right) \sum_{k=0}^{n} x^k\dbinom{n-j}{k-j} j! \\ =& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \dbinom{n}{j}\right) x^j\sum_{k=0}^{n-j} x^{k}\dbinom{n-j}{k} j! & 更改枚举下标\\ =& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \right) x^j(x+1)^{n-j} n^{\underline j} & 二项式定理\\ =&\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix}x^j(x+1)^{n-j} n^{\underline j} \\ \end{aligned} \\ \]

以下是上文所需的三个式子:

\[\begin{aligned} x^n &=\sum\limits_{i=0}^{x}\begin{Bmatrix} n\\ i\end{Bmatrix}\dbinom{x}{i}i! & 把 k^i 用第二类斯特林数打开 & (1)\\ \dbinom{n}{k}\dbinom{k}{m} &= \dbinom{n}{m}\dbinom{n-m}{k-m} & 组合意义化简& (2)\\ (x+y)^n&=\sum\limits_{i=0}^{n}\dbinom{n}{i}x^i y^{n-i} & 二项式定理& (3)\\ \end{aligned} \]

以及注意跟组合数学有关的式子有时候是可以更改枚举上界的,这是因为斯特林数或组合数在这种情况下为 \(0\)

然后你就发现第二类斯特林数 \(O(m^2)\) 求,没了。

真的没了吗?

a mistake

发现对于 \((1)\) 式,\(n=0\) 时不成立,所以要单独考虑 \(a_0\) 造成的贡献为 \(a_0(x+1)^n\)。其余的贡献是 \(\sum\limits_{i=1}^{m} a_i\sum\limits_{j=1}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix}x^j(x+1)^{n-j} n^{\underline j}\)

Code

代码不难。

// Author : Imakf
#include <bits/stdc++.h>

#define LL long long

LL n ,p ,m;

LL qpow(LL a ,LL b ,LL mod){
	if(b < 0) return 0;
	LL Ans = 1 % mod;
	while(b){if(b & 1) Ans = Ans * a % mod;
		a = a * a % mod ,b >>= 1;
	}return Ans;
}

const int MX = 1000 + 233;
LL a[MX] ,xp1[MX] ,x[MX] ,S[MX][MX] ,nd[MX];

int main(){
	std::cin >> n >> x[1] >> p >> m;
	for(int i = 0 ; i <= m ; ++i) std::cin >> a[i];
	
	x[0] = 1;
	S[1][1] = 1;
	nd[0] = 1;
	for(int i = 2 ; i <= m ; ++i){ // ball
		for(int j = 1 ; j <= i ; ++j){ // box
			S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j) % p;
			// printf("S[%d][%d] = %lld\n" ,i ,j ,S[i][j]);
		}
		x[i] = x[i - 1] * x[1] % p; 
	}
	for(int i = 0 ; i <= m ; ++i) xp1[i] = qpow(x[1] + 1 ,n - i,p);
	for(int i = 1 ; i <= m ; ++i) nd[i] = nd[i - 1] * (n - i + 1) % p;

	LL Ans = a[0] * xp1[0] % p;
	for(int i = 1 ; i <= m ; ++i){
		for(int j = 1 ; j <= i ; ++j){
			Ans = (Ans + a[i] * S[i][j] % p * x[j] % p * xp1[j] % p * nd[j]) % p;
			// printf("%lld\n" ,Ans);
		}
	}
	std::cout << Ans << std::endl;
	return 0;
}
原文地址:https://www.cnblogs.com/imakf/p/13635077.html