国家集训队 Crash 的文明世界（第二类斯特林数+换根dp）

题意

题目链接：https://www.luogu.org/problem/P4827

给定一棵 \(n\) 个节点的树和一个常数 \(k\) ，对于树上的每一个节点 \(i\) ，求出 \(\displaystyle \sum_{i=1}^n{\rm dist}^k(i,j)\)，其中 \(\rm{dist}\) 函数表示树上两点距离。

\(1 \leq n \leq 50000\)

\(1\leq k \leq 150\)

思路

看到求答案 \(k\) 次方的问题，应该联想到第二类斯特林数，因为第二类斯特林数有如下的式子：

\[n^m=\sum_{i=0}^{+\infty}{n\choose i}\left\{{m\atop i}\right\}i!
\]

可以理解成，\(n^m\) 表示把 \(m\) 个不同的球放在 \(n\) 个不同的盒子中；后面的组合数表示从 \(n\) 个盒子中选出 \(i\) 个，斯特林数表示把 \(m\) 个球分成 \(i\) 个无序集合，阶乘表示排列。另外，循环上界写乘 \(n\)，\(m\) 或者无穷大都是一样的。

假设我们已经维护住了 \(n^m\) ，我们现在想知道 \((n+1)^m\) ，怎么办呢？套入上面的式子，我们得到：

\[\begin{align*}
(n+1)^m&=\sum_{i=0}^m{n+1\choose i}\left\{{m\atop i}\right\}i!\\
&=\sum_{i=0}^m{\huge(}{n\choose i}+{n\choose i-1}{\huge)}\left\{{m\atop i}\right\}i!
\end{align*}
\]

我们发现，与 \(n^m\) 的展开式相比，\(\displaystyle \left\{{m\atop i}\right\}i!\) 没有变，每个组合数都加上前一项。这似乎在启示我们把组合数独立出来。定义数组 \(\{a_n\}\) ，用 \(a_i\) 表示 \(\displaystyle\left\{{m\atop i}\right\}i!\) 的系数，于是，我们得到了一个“数据结构”，能维护一个 \(n^m\) 形式的数，支持给 \(n\) 加一。不难发现，加上前一项的操作可以把过程逆转，于是这个“数据结构”也能支持给 \(n\) 减一，我们姑且称之为“斯特林机”（名字瞎取的，勿喷）。

只能维护一个数也太鸡肋了吧？但我们不难发现，只要 \(m\) 相同，多个 \(n^m\) 形式的数可以一起维护，直接把每个斯特林机的 \(a_i\) 加在一起即可，我们可以称之为合并两个斯特林机；类似的，我们也可以从一个斯特林机中减去另一个斯特林机。这个 \(\{a_i\}\) 数组就像插值一样，用一些方便计算的量整体运算，从而得到最后结果。

依靠斯特林机，这道题似乎就变得异常的简单。我们先考虑如何求出 \(1\) 号节点的答案。

定义 \(dp_u\) 为 \(\displaystyle\sum_{v\in{\rm subtree(u)}}{\rm dist}^k(u,v)\) 。由于都是 \(k\) 次方，那可以把 \(dp_u\) 开成一个斯特林机的形式。初值每个节点的斯特林机中只有自己，为 \(0^0\)，每次转移就对儿子的斯特林机执行各元素加一的操作，再加到自己身上。于是，我们得到了以 \(1\) 为根点答案。然后我们发现，转移中每种操作都能找到其对应的逆操作，于是我们可以很快的写出一个换根 \(dp\) 。

代码

重载了很多运算符，看着挺优美的。

#include<bits/stdc++.h>

#define FOR(i, x, y) for(int i = (x), i##END = (y);i <= i##END; ++i)

#define DOR(i, x, y) for(int i = (x), i##END = (y);i >= i##END; --i)

template<typename T, typename _T>inline bool chk_min(T &x, const _T y){return y < x? x = y, 1 : 0;}

template<typename T, typename _T>inline bool chk_max(T &x, const _T y){return x < y? x = y, 1 : 0;}

typedef long long ll;

const int N = 50005;

const int P = 10007;

const int M = 153;

int C[M][M], S[M][M], fac[M];

inline void plseq(int &x, int y) {(x += y) >= P ? x -= P : 0;}

inline void mnseq(int &x, int y) {(x -= y) < 0 ? x += P : 0;}

template<const int N, const int M, typename T> struct Linked_List

{

    int head[N], nxt[M], tot; T to[M];

    Linked_List() {clear();}

    T &operator [](const int x) {return to[x];}

    void clear() {memset(head, -1, sizeof(head)), tot = 0;}

    void add(int u, T v) {to[tot] = v, nxt[tot] = head[u], head[u] = tot++;}

    #define EOR(i, G, u) for(int i = G.head[u]; ~i; i = G.nxt[i])

};

int sm;

struct Stirling_Machine

{

	int a[M];

	Stirling_Machine() {}

	Stirling_Machine(int v) {FOR(i, 0, sm) a[i] = C[v][i];}

	void operator +=(const Stirling_Machine &_) {FOR(i, 0, sm) plseq(a[i], _.a[i]);}

	void operator -=(const Stirling_Machine &_) {FOR(i, 0, sm) mnseq(a[i], _.a[i]);}

	void operator ++() {DOR(i, sm, 1) plseq(a[i], a[i - 1]);}

	void operator --() {FOR(i, 1, sm) mnseq(a[i], a[i - 1]);}

	int query()

	{

		int ans = 0;

		FOR(i, 0, sm) plseq(ans, 1ll * a[i] * S[sm][i] % P * fac[i] % P);

		return ans;

	}

};

Linked_List<N, N << 1, int> G;

Stirling_Machine dp[N];

int ans[N];

int n;

void dfs(int u, int f)

{

	dp[u] = Stirling_Machine(0);

	EOR(i, G, u)

	{

		int v = G[i];

		if(v == f) continue;

		dfs(v, u);

		++dp[v];

		dp[u] += dp[v];

	}

}

void redfs(int u, int f)

{

	ans[u] = dp[u].query();

	EOR(i, G, u)

	{

		int v = G[i];

		if(v == f) continue;

		dp[u] -= dp[v];

		--dp[v];

		++dp[u];

		dp[v] += dp[u];

		redfs(v, u);

		dp[v] -= dp[u];

		--dp[u];

		++dp[v];

		dp[u] += dp[v];

	}

}

int main()

{

	fac[0] = fac[1] = 1;

	FOR(i, 2, M - 1) fac[i] = 1ll * fac[i - 1] * i % P;

	FOR(i, 0, M - 1) FOR(j, 0, i)

		C[i][j] = (j == 0 || j == i ? 1 : (C[i - 1][j - 1] + C[i - 1][j]) % P);

	S[0][0] = 1;

	FOR(i, 1, M - 1) FOR(j, 1, i)

		S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % P;

	scanf("%d%d", &n, &sm);

	FOR(i, 1, n - 1)

	{

		int u, v;

		scanf("%d%d", &u, &v);

		G.add(u, v), G.add(v, u);

	}

	dfs(1, 0);

	redfs(1, 0);

	FOR(i, 1, n) printf("%d\n", ans[i]);

	return 0;

}

巴特西

国家集训队 Crash 的文明世界（第二类斯特林数+换根dp）

题意

思路

代码

最新文章

热门文章