BZOJ3625 小朋友和二叉树

文章目录

题目在 cf 上也有
注:本题方法正确,但是代码只能在 cf 上通过,在 BZOJ 上不行,大概是因为 BZOJ 评测机问题

题解

这题和 3684有点像,都由生成函数解决
首先求出点权集合的生成函数
$$ C(x)=\sum_{i\in c}x^i $$
设生成合法二叉树方案的 $OGF$ 为 $F(x)$ ,则
$$ F(x)=F^2(x)C(x)+1 $$

从组合意义上来看,就是说一个子树的方案为根节点两个儿子的方案数乘积乘上自己可能选的权值的生成函数,当子树为空时方案为 $1$
这里再解释一下, $[x^n]F^2(x)$ 代表将两颗儿子的子树合起来的方案数,但是由于当前点也有权值(假设为 $i$ ),所以在新树中 $x^{n+i}$ 的系数才是代表的答案,所以要乘上 $x^i$
我刚开始认为后面的 $+1$ 应该改成 $+C(x)$ ,因为叶子节点也有权值限制,但是后来发现叶子节点可以直接看成两颗空的方案为 $1$ 的子树拼接而成
接下来继续说如何推式子
首先解这个关于 $F(x)$ 的二次方程,解得
$$ F(x)=\cfrac{1\pm \sqrt{1-4C(x)}}{2C(x)} $$
分子有理化
$$ F(x)=\cfrac{2}{1\pm \sqrt{1-4C(x)}} $$
由于式子有意义,而底下取减号时分母可能为 $0$ ,所以
$$ F(x)=\cfrac{2}{1+ \sqrt{1-4C(x)}} $$
此时对 $C(x)$ 做一些求逆,开根等运算就行了

代码

评测情况
cf.png
bzoj.png

#define MAX_N 300007
#define MOD 998244353
#define G 3
#define reg register
typedef long long ll;

int N, T;
int g[MAX_N], f[MAX_N], a[MAX_N], b[MAX_N], tmp[MAX_N], tmp2[MAX_N];
int r[MAX_N];
int inv2;

inline int quick_pow (reg int x, reg int p) {
    reg int ans = 1;
    while (p) {
        if (p & 1) ans = (int)((ll)ans * (ll)x % MOD);
        x = (int)((ll)x * (ll)x % MOD);
        p >>= 1;
    }
    return ans % MOD;
}

inline void NTT (reg int *A, reg int M, reg int type) {
    for (reg int i = 0; i < M; ++i)
        if (i < r[i])
            std::swap(A[i], A[r[i]]);
    for (reg int i = 1; i < M; i <<= 1) {
        reg int gn = quick_pow(G, (MOD - 1) / (i << 1));
        if (type == -1)
            gn = quick_pow(gn, MOD - 2);
        for (reg int j = 0, L = i << 1; j < M; j += L) {
            reg int g = 1, x, y;
            for (reg int k = 0; k < i; ++k) {
                x = A[j + k] % MOD, y = (int)((ll)A[j + i + k] * (ll)g % MOD);
                A[j + k] = (int)((ll)x + (ll)y % MOD), A[j + i + k] = (int)(((ll)x - (ll)y + MOD) % MOD);
                g = (int)((ll)g * (ll)gn % MOD);
            }
        }
    }
    if (type == 1) return;
    for (reg int i = 0; i < M; ++i)
        A[i] = (int)((ll)A[i] * (ll)quick_pow(M, MOD - 2) % MOD);
}

void transinv (reg int deg, reg int *a, reg int *b) {
    if (deg == 1) {
        b[0] = quick_pow(a[0], MOD - 2);
        return;
    }
    transinv((deg + 1) >> 1, a, b);
    reg int M = 1, len = 0;
    while (M < (deg << 1)) M <<= 1, ++len;
    for (reg int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    for (reg int i = 0; i < deg; ++i)
        tmp[i] = a[i];
    for (reg int i = deg; i < M; ++i)
        tmp[i] = 0;
    NTT(tmp, M, 1), NTT(b, M, 1);
    for (reg int i = 0; i < M; ++i)
        b[i] = (int)((2LL - (ll)b[i] * (ll)tmp[i] % MOD + MOD) % MOD * (ll)b[i] % MOD);
    NTT(b, M, -1);
    for (reg int i = deg; i < M; ++i)
        b[i] = 0;
}

void transsqrt (reg int deg, reg int *a, reg int *b) {
    if (deg == 1) {
        b[0] = a[0];
        return;
    }
    transsqrt((deg + 1) >> 1, a, b);
    for (reg int i = 0, ed = deg << 1; i < ed; ++i)
        tmp2[i] = 0;
    transinv(deg, b, tmp2);
    reg int M = 1, len = 0;
    while (M < (deg << 1)) M <<= 1, ++len;
    for (reg int i = 0; i < deg; ++i)
        tmp2[i] = (int)((ll)tmp2[i] * (ll)inv2 % MOD);
    for (reg int i = deg; i < M; ++i)
        tmp2[i] = 0;
    for (reg int i = 0; i < deg; ++i)
        tmp[i] = a[i];
    for (reg int i = deg; i < M; ++i)
        tmp[i] = 0;
    NTT(b, M, 1), NTT(tmp, M, 1), NTT(tmp2, M, 1);
    for (reg int i = 0; i < M; ++i)
        b[i] = (int)(((ll)b[i] * (ll)b[i] % MOD + (ll)tmp[i]) % MOD * tmp2[i] % MOD);
    NTT(b, M, -1);
    for (reg int i = deg; i < M; ++i)
        b[i] = 0;
}

inline void input () {
    read(T), read(N);
    int val;
    for (int i = 1; i <= T; ++i) {
        read(val);
        g[val] = MOD - 4;
    }
    g[0] = 1;
    N++;
    inv2 = quick_pow(2, MOD - 2);
}

inline void solve () {
    transsqrt(N, g, f);
    f[0] += 1;
    memset(tmp, 0, sizeof(tmp));
    memset(g, 0, sizeof(g));
    transinv(N, f, g);
    for (int i = 1; i < N; ++i)
        printf("%d\n", (g[i] << 1) % MOD);
}

int main () {
    input();
    solve();
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注