bzoj 2159 Crash 的文明世界 & hdu 4625 JZPTREE —— 第二类斯特林数+树形DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2159

使用公式：\( n^{k} = \sum\limits_{i=0}^{k} S(k,i) * i! * C_{n}^{i} \)

所以维护 \( f[x][i] = \sum\limits_{u\in subtree[x],d=dist(x,u)} C_{d}^{i} \)

然后利用 \( C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1} \)，可以树形DP过程中维护(原来想着可以线段树维护矩阵来着，呵呵)。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=,xm=,mod=;

int n,m,hd[xn],ct,to[xn<<],nxt[xn<<],f[xn][xm],g[xm],t[xn][xm];

int ans[xn],s[xm][xm],jc[xm];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void dfs(int x,int fa)

{

  f[x][]=;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa)continue;

      dfs(u,x);

      f[x][]=upt(f[x][]+f[u][]);

      for(int k=;k<=m;k++)f[x][k]=upt(f[x][k]+f[u][k]+f[u][k-]);

    }

}

void dfsx(int x,int fa)

{

  if(!fa)memcpy(t[x],f[x],sizeof f[x]);

  else

    {

      t[x][]=upt(f[x][]+g[]);

      for(int k=;k<=m;k++)t[x][k]=upt(f[x][k]+g[k]+g[k-]);//sum of C(d,k)

    }

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

      ans[x]=(ans[x]+(ll)s[m][i]*jc[i]%mod*t[x][i])%mod;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa)continue;

      g[]=upt(t[x][]-f[u][]);

      for(int k=;k<=m;k++)g[k]=upt(t[x][k]-(f[u][k]+f[u][k-]));

      dfsx(u,x);

    }

}

void init()

{

  jc[]=;

  for(int i=;i<=m;i++)jc[i]=(ll)jc[i-]*i%mod;

  s[][]=;

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

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

      s[i][j]=upt(s[i-][j-]+j*s[i-][j]);

}

int main()

{

  n=rd(); m=rd(); int L=rd();

  int now=rd(),A=rd(),B=rd(),Q=rd();

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

    {

      now = (now * A + B) % Q;

      int tmp = (i < L) ? i : L;

      int x=i-now%tmp,y=i+;

      add(x,y); add(y,x);

    }

  init();

  dfs(,); dfsx(,);

  for(int i=;i<=n;i++)printf("%d\n",ans[i]);

  return ;

}

bzoj2159

update(2018.12.16)

http://acm.hdu.edu.cn/showproblem.php?pid=4625

几乎是一模一样的题；

只是在子函数里传个数组，会莫名不对...还是开成全局的了...

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=5e4+,xm=,mod=;

int n,k,hd[xn],ct,to[xn<<],nxt[xn<<],f[xn][xm],g[xm];

int jc[xm],s[xm][xm],ans[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

void init()

{

  int mx=;

  jc[]=;

  for(int i=;i<=mx;i++)jc[i]=(ll)jc[i-]*i%mod;

  s[][]=;

  for(int i=;i<=mx;i++)

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

      s[i][j]=(s[i-][j-]+(ll)s[i-][j]*j)%mod;

}

void dfs(int x,int fa)

{

  f[x][]=;//

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa)continue;

      dfs(u,x);

      for(int j=;j<=k;j++)f[x][j]=upt(f[x][j]+f[u][j]+(j?f[u][j-]:));

    }

}

/*

void dfsx(int x,int fa,int *t)

{

  if(fa)for(int i=k;i>=0;i--)t[i]=upt(t[i]+(i?t[i-1]:0));

  for(int j=0;j<=k;j++)

    ans[x]=(ans[x]+(ll)s[k][j]*jc[j]%mod*(f[x][j]+t[j]))%mod;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa)continue;

      for(int j=0;j<=k;j++)g[j]=upt(t[j]+f[x][j]-f[u][j]-(j?f[u][j-1]:0));

      dfsx(u,x,g);

    }

}

*/

int t[xn][xm];

void dfsx(int x,int fa)

{

  if(!fa)memcpy(t[x],f[x],sizeof f[x]);

  else for(int j=;j<=k;j++)t[x][j]=upt(f[x][j]+g[j]+(k?g[j-]:));

  ans[x]=;

  for(int i=;i<=k;i++)

      ans[x]=(ans[x]+(ll)s[k][i]*jc[i]%mod*t[x][i])%mod;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa)continue;

      for(int j=;j<=k;j++)g[j]=upt(t[x][j]-(f[u][j]+(j?f[u][j-]:)));

      dfsx(u,x);

    }

}

int main()

{

  int T=rd(); init();

  while(T--)

    {

      ct=; memset(hd,,sizeof hd);

      memset(f,,sizeof f); memset(g,,sizeof g);

      n=rd(); k=rd();

      for(int i=,x,y;i<n;i++)x=rd(),y=rd(),add(x,y),add(y,x);

      dfs(,); dfsx(,);

      for(int i=;i<=n;i++)printf("%d\n",ans[i]);

    }

  return ;

}

hdu 4625