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

不错的树形$ DP$的题

可为什么我自带大常数啊$ cry$

链接：here

题意：给定一棵$ n$个节点的树，边权为$ 1$，对于每个点$ x$求$ \sum\limits_{i=1}^n dist(x,i)^k$

数据范围：$ n<=50000，k<=150$

$ Solution$

直接推式子

上下$ DP$先考虑子树内的贡献

有$ in(x)^k=\sum\limits (in(son[x])+1)^k$

这是因为自己子树内的每个点到自己的距离都$ ++$

再考虑子树外的贡献

有$ out(x)^k=(out(fa[x])+1)^k+(in(fa[x])+1)^k-(in(x)+2)^k$

这是因为父亲节点子树外的节点和父亲子树中除自己外其他子树内的节点到自己的距离相比原先都$ ++$

而自己这棵子树内不增反减所以再$ -=2$

直接二项式展开是$ nk^2$的

不过这类式子可以转化成斯特林数

我们只要从求$ in(x)^k/out(x)^k$转化成求$ C_{in(x)/out(x)}^k$即可

这样$ C_{in(x)}^k=\sum\limits C_{in(son[x])+1}^k=\sum\limits C_{in(son[x])}^k+C_{in(son[x])}^{k-1}$

求$ out$的时候同理，唯一的区别是$ C_{in(x)+2}^k$需要展开两层

代码还是比较清真的

$ my \ code$

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define p 10007

#define M 100010

#define rt register int

#define ll long long

using namespace std;

inline ll read(){

    ll x = ; char zf = ; char ch = getchar();

    while (ch != '-' && !isdigit(ch)) ch = getchar();

    if (ch == '-') zf = -, ch = getchar();

    while (isdigit(ch)) x = x *  + ch - '', ch = getchar(); return x * zf;

}

void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}

void writeln(const ll y){write(y);putchar('\n');}

int i,j,k,m,n,x,y,z,cnt;

int val[][],out[][],fa[];

int F[M],L[M],N[M],a[M];

void add(int x,int y){

    a[++k]=y;

    if(!F[x])F[x]=k;

    else N[L[x]]=k;

    L[x]=k;

}

void dfs(int x,int pre){

    fa[x]=pre;val[x][]=;

    for(rt i=F[x];i;i=N[i])if(a[i]!=pre){

        dfs(a[i],x);

        (val[x][]+=val[a[i]][])%=p;

    }

    out[x][]=n-val[x][];

}

void get(int x){

    for(rt i=F[x];i;i=N[i])if(a[i]!=fa[x]){

        get(a[i]);

        for(rt j=;j<=m;j++)

        (val[x][j]+=val[a[i]][j]+val[a[i]][j-])%=p;

    }

}

int S[][],inv[];

void up(int x){

    for(rt j=;j<=m;j++)

    if(x==)out[x][j]=;

    else out[x][j]=(out[fa[x]][j]+out[fa[x]][j-]+val[fa[x]][j]+val[fa[x]][j-]-(val[x][j-]*+val[x][j]+val[x][j-]))%p;

    for(rt i=F[x];i;i=N[i])if(a[i]!=fa[x])up(a[i]);

}

int main(){

    n=read();m=read();

    for(rt i=;i<n;i++){

        x=read();y=read();

        add(x,y);

        add(y,x);

    }

    dfs(,);get();up();

    for(rt i=;i<=n;i++)

    for(rt j=;j<=m;j++)val[i][j]+=out[i][j];

    S[][]=;

    for(rt i=;i<=m;i++)

    for(rt j=;j<=i;j++)

    S[i][j]=(S[i-][j-]+j*S[i-][j])%p;

    inv[]=inv[]=;

    for(rt i=;i<=m+;i++)inv[i]=inv[p%i]*(p-p/i)%p;

    for(rt i=;i<=n;i++){

        ll ans=,C=,jc=;

        for(rt j=;j<=m;j++){

            (ans+=val[i][j]*S[m][j]*jc)%=p;

            jc=jc*(j+)%p;

        }

        writeln((ans+p)%p);

    }

    return ;

}

巴特西

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

最新文章

热门文章