[HDU4625] JZPTREE [二类斯特林] [树形DP]

[HDU4625] JZPTREE [二类斯特林] [树形DP]

​​传送门​​

由于太弱打不出下降幂，下降幂部分请自己联想

感谢 csdn 没有让我打出下降幂，原来推了好久的下降幂式子结果就是个组合恒等式

然后直接 DP 维护下降幂，从儿子走一遍，从父亲走一遍

从父亲走的要减去从儿子走上去再走下来的， 最后在用斯特林还原就可以了

#include#include#define N 50050#define M 505using namespace std;const int Mod = 10007;int add(int a, int b){ return (a + b) % Mod;}int mul(int a, int b){ return a * b % Mod;}int T, n, m;int s[M][M], f[N][M];int first[N], nxt[N<<1], to[N<<1], tot;void addedge(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}void dfs1(int u, int fa){ f[u][0] = 1; for(int i = 1; i <= m; i++) f[u][i] = 0; for(int e = first[u]; e; e = nxt[e]){ int t = to[e]; if(t == fa) continue; dfs1(t, u); f[u][0] = add(f[u][0], f[t][0]); for(int i = 1; i <= m; i++) f[u][i] = add(f[u][i], add(f[t][i], mul(i, f[t][i-1]))); }}void dfs2(int u, int fa){ if(fa){ for(int i = m; i >= 2; i--){ f[u][i] = add(f[fa][i], mul(f[fa][i-1], i)); f[u][i] = add(f[u][i], Mod - mul(2 * i, f[u][i-1])); f[u][i] = add(f[u][i], Mod - mul(mul(i, i-1), f[u][i-2])); } f[u][1] = add(add(f[fa][1], f[fa][0]), Mod - f[u][0] * 2); f[u][0] = f[fa][0]; } for(int i = first[u]; i; i = nxt[i]) if(to[i] != fa) dfs2(to[i], u);}void FSYolanda(){ memset(first, 0, sizeof(first)); tot = 0; scanf("%d%d", &n, &m); for(int i = 1; i < n; i++){ int x, y; scanf("%d%d", &x, &y); addedge(x, y); addedge(y, x); } dfs1(1, 0); dfs2(1, 0); for(int i = 1; i <= n; i++){ int ans = 0; for(int j = 0; j <= m; j++) ans = add(ans, mul(s[m][j], f[i][j])); printf("%d\n", ans); } }int main(){ scanf("%d", &T); s[0][0] = 1; for(int i = 1; i <= M - 5; i++){ for(int j = 1; j <= i; j++) s[i][j] = add(s[i-1][j-1], mul(j, s[i-1][j])); } while(T--) FSYolanda(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。