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

（O(nlogn)求第一类斯特林数一行的方法：https://www.mina.moe/archives/11349）

第二类斯特林数的公式： \( x^{n}=\sum\limits_{k=0}^{n}C_{x}^{k}*k!*S(n,k) \)

所以一个点 t 的答案为　　\( \sum\limits_{j=1}^{N} \sum\limits_{l=0}^{k}S(k,l)*l!*C_{dis(t,j)}^{l} \)

　　　　　　　　　　　　\( = \sum\limits_{l=0}^{k}S(k,l)*l! \sum\limits_{j=1}^{N}C_{dis(t,j)}^{l} \)

然后开始把那个 C 拆开什么的。最后去看题解了。

原来那个 C 已经可以树形DP算了。设 \( f[ i ][ j ] = \sum\limits_{k=1}^{N}C_{dis(i,k)}^{j} \) ，由 \( C_{i}^{j}=C_{i-1}^{j}+C_{i-1}^{j-1} \) 可以得到递推式（换根时）：

　　\( f[i][j]-=f[v][j-1]+f[v][j] \)　　\( f[v][j]=f[i][j-1]+f[i][j] \)　　（其中 i 是现在的根， v 是下一次的根）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=5e4+,M=,mod=;

int n,m,hd[N],xnt,to[N<<],nxt[N<<];

int f[N][M],g[N][M],s[M][M],jc[M];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

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

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

  return fx?ret:-ret;

}

void upd(int &x){x>=mod?x-=mod:;}

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

void init()

{

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

  s[][]=;

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

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

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

}

void cz(int *a,int *b,int fx)

{

  a[]=(a[]+mod+b[]*fx)%mod;

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

    a[j]=(a[j]+(b[j-]+b[j])*fx)%mod+mod,upd(a[j]);

}

void dfs(int cr,int fa)

{

  f[cr][]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    dfs(v,cr);

    cz(f[cr],f[v],);

      }

  memcpy(g[cr],f[cr],sizeof f[cr]);

}

void dfsx(int cr,int fa)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    cz(g[cr],f[v],-);

    cz(g[v],g[cr],);

    dfsx(v,cr);

    cz(g[cr],f[v],);

      }

}

int main()

{

  int L,now,A,B,Q,tmp,u,v;

  scanf("%d%d%d",&n,&m,&L); init();

  scanf("%d%d%d%d",&now,&A,&B,&Q);

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

    {

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

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

      u=i-now%tmp; v=i+;

      add(u,v); add(v,u);

    }

  dfs(,); dfsx(,);

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

    {

      int ans=;

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

    ans=(ans+s[m][j]*jc[j]%mod*g[i][j])%mod;

      printf("%d\n",ans);

    }

  return ;

}

UPD（2018.12.16）：今天讲到 hdu 4625 ，竟然完全不记得做过。于是又打了一遍。hdu 交上去总是 CE ，重打了一遍 init( ) 里的括号就好了。难道是什么中文括号之类的？

不过今天讲的是另一种想法，维护 x 的 n 次下降幂之类的。不管了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=5e4+,M=,mod=;

int T,n,m,hd[N],xnt,to[N<<],nxt[N<<];

int S[M][M],jc[M],f[N][M],ans[N];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

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

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

  return fx?ret:-ret;

}

void upd(int &x){while(x>=mod)x-=mod;while(x<)x+=mod;}

void init()

{

  int lm=;

  S[][]=;

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

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

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

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

}

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

void add(int *a,int *b,int k)

{

  a[]+=b[]*k;

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

    a[j]+=(b[j-]+b[j])*k,upd(a[j]);

}

void dfs(int cr,int fa)

{

  f[cr][]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    dfs(v,cr);add(f[cr],f[v],);

      }

}

void dfsx(int cr,int fa)

{

  ans[cr]=;

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

    ans[cr]=(ans[cr]+(ll)jc[i]*S[m][i]%mod*f[cr][i])%mod;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    add(f[cr],f[v],-);

    add(f[v],f[cr],);

    dfsx(v,cr);

    add(f[v],f[cr],-);

    add(f[cr],f[v],);

      }

}

int main()

{

  T=rdn();init();

  while(T--)

    {

      n=rdn();m=rdn();

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

      for(int i=,u,v;i<n;i++)

    u=rdn(),v=rdn(),add(u,v),add(v,u);

      memset(f,,sizeof f);

      dfs(,);dfsx(,);

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

    }

  return ;

}

秒客网

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

相关文章