Luogu

BZOJ

分析

把原来的柿子拆掉:

$$ \begin{aligned} S(u)&=\sum_{v=1}^N \mathrm{dist}(u,v)^k\\ &=\sum_{v=1}^n \sum_{i=0}^k S(k,i)C_{\mathrm{dist}(u,v)}^i\,i!\\ &=\sum_{i=0}^kS(k,i)\,i!\,\sum_{v=1}^nC_{\mathrm{dist}(u,v)}^i \end{aligned} $$

前面的可以预处理,后面的可以先做一遍树形DP,再用换根法求出每个点的$g(u)=\sum\limits_{v=1}^n\,C_{\mathrm{dist}(u,v)}^i$,最后加起来就是每个点的答案。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=50000+10;
const int MAXK=150+10;
const int MOD=10007;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n,k;
int S[MAXK][MAXK],fact[MAXK];
int f[MAXN][MAXK],g[MAXN][MAXK];

inline void Dfs(int u,int fa) {
    f[u][0]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        Dfs(v,u);
        for (re int j=0;j<=k;++j) f[u][j]=(f[u][j]+f[v][j])%MOD;
        for (re int j=1;j<=k;++j) f[u][j]=(f[u][j]+f[v][j-1])%MOD;
    }
}

int tmp[MAXK];

inline void reDfs(int u,int fa) {
    for (re int j=0;j<=k;++j) g[u][j]=f[u][j];
    if (fa) {
        for (re int j=0;j<=k;++j) tmp[j]=(g[fa][j]-f[u][j]+MOD)%MOD;
        for (re int j=1;j<=k;++j) tmp[j]=(tmp[j]-f[u][j-1]+MOD)%MOD;
        for (re int j=0;j<=k;++j) g[u][j]=(g[u][j]+tmp[j])%MOD;
        for (re int j=1;j<=k;++j) g[u][j]=(g[u][j]+tmp[j-1])%MOD;
    }
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa) reDfs(e[i].v,u);
}

int main() {
//Luogu上的输入
    n=read(),k=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v);
        addEdge(v,u);
    }
//BZOJ上的输入
    n=read(),k=read();
    int L=read(),now=read(),A=read(),B=read(),Q=read();
    for (re int i=1;i<n;++i) {
        now=(now*A+B)%Q;
        int tmp=i<L?i:L;
        int u=i-now%tmp,v=i+1;
        addEdge(u,v); addEdge(v,u);
    }
//输入End
    fact[0]=1;
    for (re int i=1;i<=k;++i) fact[i]=fact[i-1]*i%MOD;
    S[0][0]=1;
    for (re int i=1;i<=k;++i)
        for (re int j=1;j<=i;++j)
            S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%MOD;
    Dfs(1,0); reDfs(1,0);
    for (re int i=1;i<=n;++i) {
        int ans=0;
        for (re int j=0;j<=k;++j)
            ans=(ans+S[k][j]*fact[j]%MOD*g[i][j]%MOD)%MOD;
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 48 PM