atcoder2064 Many Easy Problems

题意翻译

给定一棵无根树,定义$f(i)$,对于所有大小为$i$的点集,求出能够包含它的最小连通块大小之和。对于$i=1 \to n$的所有$i$,求出$f(i)$。

注意模数。

题目描述

高橋君はある日青木君から以下の様な問題を貰いました。

  • $ N $ 頂点の木と、整数 $ K $ が与えられる。木の頂点は $ 1,2,...,N $ と番号がついているものとし、辺は $ (a_i,\ b_i) $ で表す。

  • 頂点の集合 $ S $ について $ f(S) $ を、 $ S $ をすべて含む部分木の頂点数の最小値とする

  • 木から $ K $ 個の頂点を選ぶ方法は $ _NC_K $ 通りあるが、それぞれについて選んだ頂点を $ S $ とし、 $ f(S) $ の総和を求める

  • 答えは大きくなることがあるので、 $ 924844033 $ (素数) で割ったあまりを出力する

高橋君にとってこの問題は簡単すぎました。なので $ K\ =\ 1,2,...,N $ 全てについてこの問題を解くことにしました。

输入格式

The input is given from Standard Input in the following format:

 $ N $ 
 $ a_1 $   $ b_1 $ 
 $ a_2 $   $ b_2 $ 
 $ : $ 
 $ a_{N-1} $   $ b_{N-1} $ 

输出格式

Print $ N $ lines. The $ i $ -th line should contain the answer to the problem where $ K=i $ , modulo $ 924844033 $ .

样例输入

7
1 2
2 3
2 4
4 5
4 6
6 7

样例输出

7
67
150
179
122
45
7

说明

$ 2\le N\le 200,000 $

$ 1\le a_i,b_i\le N $


分析

数据范围$O(n\log n)$级别,又要输出$f(1),\dots,f(n)$,大概率是FFT。

显然我们不可能枚举每个大小为$k$的点集,逐个去求连通块大小。换一种思路,我们可以枚举每个点$u$,计算它对几个大小为$k$的点集有贡献。这里的有贡献,指点集构成的连通块包含$u$。

连通块包含$u$的点集个数不好求,正难则反,考虑求连通块不包含$u$的大小为$k$的点集个数。可以发现点集中的所有点必须同在$u$的某个子树中(往$u$父亲方向那棵子树也算)。

那么$u$对$f(k)$的贡献为:$C(n,k)-\sum_{v} {C(siz(v),k)}$

则$f(k)=\sum_u{[C(n,k)-\sum_{v} {C(siz(v),k)}]}$

直接做是$O(n^3)$的,但是可以发现,不管$k$取多少,求$f(k)$时每个$C(i,k)$的系数都是不变的,只与树的形态有关。所以我们可以在预处理时$O(n)$求出$C(i,k)$的系数,记为$a_i$。

现在问题转化成:

$$f(k)=\sum_{k\le i\le n}a_i\cdot C(i,k)$$

拆开组合数:

$$f(k)=\sum_{k\le i\le n}a_i\cdot \frac{i!}{k!(i-k)!}$$

$$k!\cdot f(k)=\sum_{k\le i\le n}(a_i\cdot i!)\cdot \frac{1}{(i-k)!}$$

设$g(i)=a_{n-i}\cdot (n-i)!$,$h(i)=\frac{1}{i!}$,求出$s=g\cdot h$,则$f(k)=\frac{1}{k!}\cdot s(n-k)$

多项式卷积使用NTT,注意题目的模数原根为$5$。复杂度$O(n\log n)$。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 2e5+50;
const int P = 924844033;

struct Graph {
    struct Edge {
        int to, nxt;
    } e[N<<1];
    int top, head[N];

    Graph(): top(0) {
        memset(head, -1, sizeof head);
    }

    void add(int u, int v) {
        e[top] = (Edge){v, head[u]};
        head[u] = top++;
    }

    void add2(int u, int v) {
        add(u, v);
        add(v, u);
    }
} G;

int n, a[N];
int siz[N];
int fac[N], ifac[N];
int g[N], h[N], s[N<<1];

int qPow(int x, int k) {
    int rtn = 1;
    for (; k; k >>= 1, x = (ll)x * x % P)
        if (k & 1) rtn = (ll)rtn * x % P;
    return rtn;
}

void dfs(int u, int fa) {
    siz[u] = 1;
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        a[siz[v]]--;
    }
    a[n]++;
    a[n-siz[u]]--;
}

void initFac() {
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (ll)fac[i-1] * i % P;
    ifac[n] = qPow(fac[n], P-2);
    for (int i = n-1; i >= 0; i--)
        ifac[i] = (ll)ifac[i+1] * (i+1) % P;
}

namespace NTT {
    const int G = 5;

    int n;
    int rev[N<<2];
    int a[N<<2], b[N<<2], t[N<<2];

    void init(int m) {
        int len = 0;
        for (n = 1; n < m; n <<= 1)
            len++;
        for (int i = 0; i < n; i++)
            rev[i] = rev[i>>1] >> 1 | (i&1) << len-1;
    }

    void NTT(int f[], int sgn) {
        for (int i = 0; i < n; i++)
            if (rev[i] > i) std::swap(f[rev[i]], f[i]);
        for (int i = 1; i < n; i <<= 1) {
            int gn = qPow(G, (P-1)/(i*2));
            if (sgn == -1) gn = qPow(gn, P-2);
            for (int j = 0; j < n; j += i*2) {
                int g = 1;
                for (int k = 0; k < i; k++, g = (ll)g * gn % P) {
                    int x = f[j+k], y = (ll)g * f[j+i+k] % P;
                    f[j+k] = (x + y) % P;
                    f[j+i+k] = (x - y) % P;
                }
            }
        }
        if (sgn == -1) {
            int invn = qPow(n, P-2);
            for (int i = 0; i < n; i++)
                f[i] = (ll)f[i] * invn % P;
        }
        for (int i = 0; i < n; i++)
            f[i] = (f[i] + P) % P;
    }

    void mul(int la, int ta[], int lb, int tb[], int res[]) {
        init(la+lb-1);
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        for (int i = 0; i < la; i++)
            a[i] = ta[i];
        for (int i = 0; i < lb; i++)
            b[i] = tb[i];
        NTT(a, 1);
        NTT(b, 1);
        for (int i = 0; i < n; i++)
            t[i] = (ll)a[i] * b[i] % P;
        NTT(t, -1);
        for (int i = 0; i < la+lb-1; i++)
            res[i] = t[i];
    }
}

int main() {
    scanf("%d", &n);
    initFac();
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G.add2(u, v);
    }
    dfs(1, 0);
    for (int i = 0; i < n; i++) {
        g[i] = ifac[i];
        h[i] = (ll)fac[n-i] * a[n-i] % P;
    }
    NTT::init(n);
    NTT::mul(n, g, n, h, s);
    for (int i = 1; i <= n; i++)
        printf("%d\n", (int)((ll)s[n-i] * ifac[i] % P));
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论