Crash的文明世界-第二类斯特林数+树形DP

2018-06-23 10:46:42         来源：Maxwei_wzj的OI世界

nk=i=0kS(k,i)i!Cni" role="presentation">$nk=∑i=0kS(k,i)?i!?Cni$

S(i)=j=1np=0kS(k,p)p!Cdist(i,j)p" role="presentation">$S(i)=∑j=1n∑p=0kS(k,p)?p!?Cdist(i,j)p$
=p=0kS(k,p)p!j=1nCdist(i,j)p" role="presentation">$=∑p=0kS(k,p)?p!?∑j=1nCdist(i,j)p$

```#include
using namespace std;
const int mod=10007;
int n,k,first[50010]={0},tot=0;
int S[160][160]={0},fac[160],down[50010][160]={0},up[50010][160]={0};
struct edge
{
int v,next;
}e[100010];

void insert(int a,int b)
{
e[++tot].v=b;
e[tot].next=first[a];
first[a]=tot;
}

void init()
{
int i,now,l,A,B,Q,tmp;

scanf("%d%d%d",&n,&k,&l);
scanf("%d%d%d%d",&now,&A,&B,&Q);
for(i=1;i1)
{
for(int i=1;i<=k;i++)
{
up[v][i]=(up[fa][i]+up[fa][i-1])%mod;
up[v][i]=((up[v][i]+down[fa][i]-down[v][i]-down[v][i-1])%mod+mod)%mod;
up[v][i]=((up[v][i]+down[fa][i-1]-down[v][i-1])%mod+mod)%mod;
if (i>1) up[v][i]=(up[v][i]-down[v][i-2]+mod)%mod;
else up[v][i]=(up[v][i]-1+mod)%mod;
}
}
for(int i=first[v];i;i=e[i].next)
if (e[i].v!=fa) calc_up(e[i].v,v);
}

void solve()
{
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=1;j<=k;j++)
ans=(ans+S[k][j]*fac[j]%mod*(down[i][j]+up[i][j]))%mod;
printf("%d\n",ans);
}
}

int main()
{
init();
calc_down(1,0);
calc_up(1,0);
solve();

return 0;
}```