bzoj2159

树形dp+第二类斯特林数

又是这种形式，只不过这次不用伯努利数了

直接搞肯定不行，我们化简一下式子，考虑x^n的组合意义，是把n个物品放到x个箱子里的方案数。那么就等于这个i=1->n,sigma(s[n,i]*A(x,i)),就是枚举要分成几组，这个用斯特林数算，然后把这些组放进箱子里，那么就是A(x,i),A是排列，但是这样还是不行，我们把A(x,i)=C(x,i)*i!,这样就行了，阶乘和斯特林数可以提出来，只要预处理一个点的组合数就行了，也就是∑i=1->n ∑ j=1->k C(dis(u,i),j),这个东西我们可以利用组合数的性质dp，也就是c[i][j]=c[i-1][j]+c[i-1][j-1],记住要减去重复的

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + , M = , P = ;

int n, m, L, now, A, B, Q;

int s[M][M], up[N][M], down[N][M], fac[M];

vector<int> G[N];

void dfs(int u, int last)

{

    down[u][] = ;

    for(int i = ; i < G[u].size(); ++i)

    {

        int v = G[u][i];

        if(v == last) continue;

        dfs(v, u);

        down[u][] = (down[u][] + down[v][]) % P;

        for(int j = ; j <= m; ++j) down[u][j] = ((down[u][j] + (down[v][j - ] + down[v][j]) % P) % P) % P;

    }

}

void dfs1(int u, int last)

{

    if(last)

    {

        up[u][] = n - down[u][];

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

        {

            up[u][i] = (up[u][i] + ((up[last][i] + up[last][i - ] + down[last][i] + down[last][i - ] - down[u][i] - (down[u][i - ] << )) % P + P) % P) % P;

            if(i > ) up[u][i] = ((up[u][i] - down[u][i - ]) % P + P) % P;

        }

    }

    for(int i = ; i < G[u].size(); ++i)

    {

        int v = G[u][i];

        if(v == last) continue;

        dfs1(v, u);

    }

}

int main()

{

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

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

    {

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

        int tmp = min(i, L);

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

        G[u].push_back(v);

        G[v].push_back(u);

    }

    s[][] = fac[] = ;

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

    {

        fac[i] = fac[i - ] * i % P;

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

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

    }

    dfs(, );

    dfs1(, );

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

    {

        int ans = ;

        for(int j = ; j <= m; ++j) ans = (ans + s[m][j] * fac[j] % P * (up[i][j] + down[i][j]) % P) % P;

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

    }

    return ;

}

巴特西

bzoj2159

最新文章

热门文章