BZOJ2159 Crash的文明世界 【树形dp + Stirling数】

tonyfang posted @ 2016年8月12日 08:21 in BZOJ with tags c++ OI , 1740 阅读


$d(i) = \sum_{1\leq x \leq n}^{i \not= x}dist(x, i)^{k}$

数据范围:$1 \leq n \leq 50000, 1\leq k \leq 150$




$x^n=\sum_{1<=k<=n}S(n, k) \times F(x, k)$

其中$S(n, k)$为第二类Stirling数,$S(n, k) = S(n-1, k-1) + k \times S(n-1, k)$

$F(n, k) = n \times (n-1) \times ... \times (n-k+1)$

那么$d(i) = \sum_{j\leq k}S(k, j) \times f(i, j)$

其中$f(i,j) = \sum_{1\leq x \leq n}^{x \not= i} F(dist(i, x), j)$


但是我们发现,f数组很难通过树形dp求出。考虑到$C(n, k) = \frac{F(n, k)}{k!}$,我们更改f数组表示的内容,改为

$f'(i,j) = \sum_{1\leq x \leq n}^{x \not= i} C(dist(i, x), j)$。

那么我们就有$f(i, j) = f'(i, j) \times j!$,我们可以通过pascal定理转移出f',从而转移出f。

pascal定理:$C(n, k) = C(n-1, k) + C(n-1, k-1)$




# include <stdio.h>

using namespace std;

int n, k;
int tot=0, head[50010], to[200010], next[200010];
int f[50010][160];
int S[160][160];
int fac[160], ans[50010];

// f[i, j] = sigma(C(dist(i, x), j))
// ans[x] = sigma(S(k, j)*g[x, j])     (1<=j<=k)

inline void mad(int &x, int delta) {
	delta %= 10007;
	x = (x+delta) % 10007;
inline void msu(int &x, int delta) {
	delta %= 10007;
	x = x-delta;
	x = (x+10007) % 10007;

inline void add(int u, int v) {

inline void dp(int x, int fa) {
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dp(to[i], x);
		mad(f[x][0], f[to[i]][0]);
		for (int j=1; j<=k; ++j) mad(f[x][j], f[to[i]][j] + f[to[i]][j-1]);

int g[160], h[160];

inline void calc(int x, int fa) {
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		g[0] = f[x][0];
		msu(g[0], f[to[i]][0]);
		h[0] = n;
		for (int j=1; j<=k; ++j) {
			g[j] = f[x][j], msu(g[j], f[to[i]][j] + f[to[i]][j-1]);
			h[j] = (f[to[i]][j] + g[j] + g[j-1]) % 10007;
		for (int j=0; j<=k; ++j) {
			f[to[i]][j] = h[j];
			mad(ans[to[i]], S[k][j]*fac[j]%10007*h[j]%10007);
		calc(to[i], x);

int main() {
	int tL, tNOW, tA, tB, tC;
	scanf("%d%d%d", &n, &k, &tL);
	scanf("%d%d%d%d", &tNOW, &tA, &tB, &tC);
	for (int i=1; i<=n-1; ++i) {
		int u, v;
		u=i-tNOW%(i<tL?i:tL), v=i+1;
		//scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	int s=1;
	fac[0] = 1;
	for (int i=1; i<=k; ++i) {
		s = s * i % 10007;
		fac[i] = s;
	S[0][0] = 1;
	for (int i=1; i<=k; ++i)
		for (int j=1; j<=k; ++j)
			mad(S[i][j], S[i-1][j-1] + S[i-1][j]*j);
	for (int i=1; i<=k; ++i, printf("\n"))
		for (int j=1; j<=k; ++j)
			printf("%d ", S[i][j]);
	dp(1, 0);
	for (int i=0; i<=k; ++i) 
		mad(ans[1], S[k][i]*fac[i]%10007*f[1][i]%10007);
	calc(1, 0);
	for (int i=1; i<=n; ++i) printf("%d\n", ans[i]);
	return 0;
} 说:
2023年4月18日 17:17

Who are enthusiastic about publishing Education Updates in the public interest with transparency. dpost is an initiative of professional writers who have banded together to provide devoted news coverage of current events in India. Our team consists of professional writers and citizen journalists with a wide range of journalism interests.

登录 *

loading captcha image...
or Ctrl+Enter