BZOJ 2159: Crash 的文明世界第二类斯特林数+树形dp

这个题非常巧妙啊~

#include <bits/stdc++.h>

#define M  170

#define N  50003

#define mod 10007

#define LL long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

inline int qpow(int x,int y)

{

    int tmp=1;

    for(;y;y>>=1,x=1ll*x*x%mod)    if(y&1)   tmp=1ll*tmp*x%mod;

    return tmp;

}

int n,edges,K;

int fac[N],inv[N],g[N][M],tmp[M],hd[N],to[N<<1],nex[N<<1],S[M][M],f[N][M];

inline void addedge(int u,int v)  {  nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;   }

void dfs1(int u,int ff)

{

    f[u][0]=1;

    for(int i=hd[u];i;i=nex[i])

    {

        int v=to[i];   if(v==ff)   continue;

        dfs1(v,u);

        for(int j=0;j<=K;++j)   f[u][j]=(f[u][j]+f[v][j])%mod;

        for(int j=1;j<=K;++j)   f[u][j]=(f[u][j]+f[v][j-1])%mod;

    }

}

void dfs2(int u,int ff)

{

    for(int j=0;j<=K;++j)    g[u][j]=f[u][j];

    if(ff)

    {

        for(int j=0;j<=K;++j)    tmp[j]=g[ff][j];

        for(int j=0;j<=K;++j)    tmp[j]=(tmp[j]+mod-f[u][j])%mod;

        for(int j=1;j<=K;++j)    tmp[j]=(tmp[j]+mod-f[u][j-1])%mod;

        for(int j=0;j<=K;++j)    g[u][j]=(g[u][j]+tmp[j])%mod;

        for(int j=1;j<=K;++j)    g[u][j]=(g[u][j]+tmp[j-1])%mod;

    }

    for(int i=hd[u];i;i=nex[i])     if(to[i]!=ff)    dfs2(to[i],u);

}

inline void Read()

{

    int L,now,A,B,Q;

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

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

    {

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

        int tmp=i<L?i:L;

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

        addedge(x,y),addedge(y,x);

    }

}

int main()

{

    // setIO("input");

    int i,j;

    Read();

    S[0][0]=fac[0]=1;

    for(i=1;i<=K;++i)   fac[i]=1ll*fac[i-1]*i%mod;

    for(i=1;i<=K;++i)   for(j=1;j<=i;++j)   S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j])%mod;

    dfs1(1,0),dfs2(1,0);

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

    {

        int ans=0;

        for(j=0;j<=K;++j)    ans=(ans+1ll*S[K][j]*fac[j]%mod*g[i][j]%mod)%mod;

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

    }

    return 0;

}

巴特西

BZOJ 2159: Crash 的文明世界第二类斯特林数+树形dp

最新文章

热门文章

巴特西

BZOJ 2159: Crash 的文明世界 第二类斯特林数+树形dp

最新文章

热门文章

BZOJ 2159: Crash 的文明世界第二类斯特林数+树形dp