BZOJ 2159 Crash 的文明世界

以为是个什么 DS 题，原来还有这种操作？（似乎确实可以 DS 做）

以下 subtree(p) 表示以 p 为根的子树中所有结点的集合，son(p) 表示 p 的所有儿子的集合，fa(p) 表示 p 的父亲。

根据第二类斯特林数的某些性质，有 nk=k∑i=0i!{ki}(ni)

故 S(i)=k∑e=0e!{ke}n∑j=1(dist(i,j)e)

主要问题在于如何算 n∑j=1(dist(i,j)e)。
考虑设 fu,e=∑v∈subtree(u)(dist(u,v)e)gu,e=∑v∉subtree(u)(dist(u,v)e)

看起来 f 更好做： fu,e=(0e)+∑v∈son(u)∑w∈subtree(v)(dist(v,w)+1e)=[e=0]+∑v∈son(u)∑w∈subtree(v)[(dist(v,w)e)+(dist(v,w)e−1)]=[e=0]+∑v∈son(u)(fv,e+fv,e−1)

于是是 g： gu,e=∑v∉subtree(fa(u))(dist(fa(u),v)+1e)+∑v∈subtree(fa(u))(dist(fa(u),v)+1e)−∑v∈subtree(u)(dist(u,v)+2e)=(gfa(u),e+gfa(u),e−1)+(ffa(u),e+ffa(u),e−1)−(fu,e+2fu,e−1+fu,e−2)

然后就做完了鸭。

代码：

#include <cstdio>
using namespace std;
const int N = 5e4;
const int K = 150;
const int mod = 10007;
int n,k;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5];
int S[K + 5][K + 5],fac[K + 5];
int f[N + 5][K + 5],g[N + 5][K + 5],ans;
void dfs1(int p)
{
    f[p][0] = 1;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dfs1(to[i]),f[p][0] = (f[p][0] + f[to[i]][0]) % mod;
            for(register int j = 1;j <= K;++j)
                f[p][j] = (f[p][j] + f[to[i]][j] + f[to[i]][j - 1]) % mod;
        }
}
void dfs2(int p)
{
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            g[to[i]][0] = (g[p][0] + f[p][0] - f[to[i]][0] + mod) % mod;
            g[to[i]][1] = (g[p][1] + g[p][0] + f[p][1] + f[p][0] - f[to[i]][1] - 2 * f[to[i]][0] + mod * 3) % mod;
            for(register int j = 2;j <= K;++j)
                g[to[i]][j] = (g[p][j] + g[p][j - 1] + f[p][j] + f[p][j - 1] - f[to[i]][j] - 2 * f[to[i]][j - 1] - f[to[i]][j - 2] + mod * 4) % mod;
            dfs2(to[i]);
        }
}
int main()
{
    int L,now,A,B,Q,tmp,u,v;
    scanf("%d%d%d",&n,&k,&L),fac[0] = S[0][0] = 1;
    scanf("%d%d%d%d",&now,&A,&B,&Q);
    for(register int i = 1;i <= k;++i)
        fac[i] = fac[i - 1] * i % mod;
    for(register int i = 1;i <= k;++i)
        for(register int j = 1;j <= k;++j)
            S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % mod;
    for(register int i = 1;i < n;++i)
    {
        now = (now * A + B) % Q;
        tmp = (i < L) ? i : L;
        u = i - now % tmp,v = i + 1;
        add(u,v),add(v,u);
    }
    dfs1(1),dfs2(1);
    for(register int i = 1;i <= n;++i)
    {
        ans = 0;
        for(register int j = 0;j <= k;++j)
            ans = (ans + fac[j] * S[k][j] % mod * (f[i][j] + g[i][j]) % mod) % mod;
        printf("%d\n",ans);
    }
}