bzoj 2655: calc （组合容斥+伯努利数）

题意

传送门

题解

• 发现可以用容斥乱搞，设$f[i]$为已经选了$i$个数的互不相等的权值和，$S(n,k)$为$1-n$的$k$次前缀和，也就是$sum_{i=1}^ni^k$。
  那么 $f[i]=∑ f(i-j-1) * S(A,j+1) * (-1)^j * P(i-1,j)$ ，其中$0le j<i$
  相当于把下一个选的数作为基准，加 一个都不同的权值和 减 有一个和下一个相同的权值和 加 有两个和下一个相同的权值和…
  接下来就是求$S(n,k)$了，这个玩意好像叫伯努利数，但（$O(n^2)$求一行）并不是很难推。
  显然的是：$(n+1)^k-n^k = C(k,1)*n^{k-1} +C(k,2)*n^{k-2}+....+C(k,k)*n^0$把$n$从$1$代到$n$，等号左边和右边都加起来：
  $(n+1)^k-1=C(k,1)*S(n,k-1)+C(k,2)*S(n,k-2)+....+C(k,k)*S(n,0)$$o$
  $(n+1)^{k+1}-1=C(k+1,1)*S(n,k)+C(k+1,2)*S(n,k-1)+...+C(k+1,k+1)*S(n,0)$移项之后就可以通过$S(n,k-1),S(n,k-2).....S(n,0)$来求$S(n,k)$了 (需要求一下逆元)
• （转自JHYHH的博客，有修改）

然后对于这里的$P(i-1,j)$，我不太理解为什么是排列而不是组合。有的人是这么说的：
不太懂。。

重新考虑容斥的过程，在枚举前面有一个与当前位置相同的时候，两个的被算了两次，所以枚举两个相同的时候应该乘2=2!；而枚举三个的时候，被两个的算了3次，而两个的系数已经乘了2!，所以三个的系数就是3*2!=3!。

最后所有系数都乘上一个$j$的阶乘就变成了排列数。

CODE

#pragma GCC optimize ("O2")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
typedef long long LL;
int A, n, p, inv[MAXN], fac[MAXN], S[MAXN], c[MAXN][MAXN], f[MAXN];
inline void pre(const int mod) {
	c[0][0] = 1;
	for(int i = 1; i <= n+1; ++i) {
		c[i][0] = c[i][i] = 1;
		for(int j = 1; j < i; ++j)
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
	}
	inv[0] = inv[1] = fac[0] = fac[1] = 1;
	for(int i = 2; i <= n+1; ++i)
		inv[i] = 1ll * (mod - mod/i) * inv[mod%i] % mod,
		fac[i] = 1ll * fac[i-1] * i % mod;
	
	S[0] = A; int tmp = (A+1) % mod;
	for(int i = 1; i <= n; ++i) {
		tmp = 1ll * tmp * (A+1) % mod;
		S[i] = tmp - 1;
		for(int j = 0; j < i; ++j)
			S[i] = (S[i] - 1ll * c[i+1][i-j+1] * S[j] % mod) % mod;
		S[i] = 1ll * S[i] * inv[i+1] % mod;
	}
}
int main () {
	scanf("%d%d%d", &A, &n, &p);
	const int mod = p; pre(mod);
	f[0] = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 0, sgn = 1; j < i; ++j, sgn = -sgn)
			f[i] = (f[i] + 1ll * f[i-j-1] * S[j+1] % mod * sgn * c[i-1][j] % mod * fac[j] % mod) % mod;
	printf("%d
", (f[n] + mod) % mod);
}
//f[i]=∑ f(i-j-1) * S(A,j+1) * (-1)^j * P(i-1,j)

还有插值的做法 Orz whzzt