Liveddd's Blog

愛にできることはまだあるかい

P4827 [国家集训队] Crash 的文明世界

发表于 更新于
本文字数： 2.5k 阅读时长 ≈ 6 分钟

普通幂转下降幂的经典技巧。

注意到 $k\le 150$，很容易想到利用斯特林数，将普通幂转下降幂。即：

我们设 $f(x,i)=\sum_k \binom{x}{k}$，我们容易根据组合数的递推关系 $\binom{x}{k}=\binom {x-1}{k-1}+\binom{x-1}{k}$，直接写出转移方程：$f(x,i)=\sum_y (f(y,i)+f(y,i-1))$。再做一次换根即可。时间复杂度 $\mathcal O(nk+k^2)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=5e4+10,M=150+10,mod=1e4+7;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n,k;
int tot,head[N],ver[N<<1],ne[N<<1];
int s[M][M],fac[M];
int f[N][M],g[N][M],tmp[M];
inline int adj(int x){return x>=mod?x-mod:x;}
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs1(int x,int fa)
{
    f[x][0]=1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs1(y,x);
        for(int j=1;j<=k;j++)f[x][j]=adj(f[x][j]+adj(f[y][j-1]+f[y][j]));
        f[x][0]=adj(f[x][0]+f[y][0]);
    }
}
void dfs2(int x,int fa)
{
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        for(int j=1;j<=k;j++)
            tmp[j]=adj(adj(g[x][j]-f[y][j-1]+mod)-f[y][j]+mod);
        tmp[0]=adj(g[x][0]-f[y][0]+mod);
        for(int j=1;j<=k;j++)
            g[y][j]=adj(f[y][j]+adj(tmp[j-1]+tmp[j]));
        g[y][0]=g[x][0];
        dfs2(y,x);
    }
}


int main()
{
    read(n,k);
    for(int i=1,u,v;i<n;i++)read(u,v),add(u,v),add(v,u);
    s[0][0]=1;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=i;j++)
            s[i][j]=adj(s[i-1][j-1]+1ll*j*s[i-1][j]%mod);
    fac[0]=1;
    for(int i=1;i<=k;i++)fac[i]=1ll*fac[i-1]*i%mod;
    dfs1(1,0);
    memcpy(g[1],f[1],sizeof(f[1]));
    dfs2(1,0);
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        for(int j=0;j<=k;j++)
            ans=adj(ans+1ll*s[k][j]*fac[j]%mod*g[i][j]%mod);
        printf("%d\n",ans);
    }
    return 0;
}