【BZOJ3625】【CF438E】小朋友和二叉树

题目

传送门

思路&做法

我们可以用\(v_i\)表示\(i\)在\(c\)中出现了几次， 用\(f_i\)表示权值为\(i\)的神犇树的总数, 于是

\[ f_x = \sum_{i = 0}^{x}v_i \bigg( \sum_{j = 0}^{x-i}f_jf_{x-i-j} \bigg) \]

\[ f_0 = 1 \]

然后我们设\(v\)的生成函数为\(V = \sum_{i = 0} ^{\infty}v_ix^i\),
设\(f\)的生成函数为\(F = \sum_{i = 0}^{\infty}f_ix^i\)

所以

\[F(x) = C(x) F(x)F(x) + 1\]

然后移一下项

\[V(x)F^2(x) - F(x) + 1 = 0\]

接着直接用求根公式

\[F(x) = {1 \pm \sqrt{1 - 4 \times V(x)} \over 2 \times V(x)}\]

于是有两种情况

\((1)\)

\[F(x) = {1 + \sqrt{1 - 4 \times V(x)} \over 2 \times V(x)}\]
要舍去\((\)原因？不知道，我太弱了\()\)

\((2)\)

\[F(x) = {1 - \sqrt{1 - 4 \times V(x)} \over 2 \times V(x)}\]

可以把分子和分母同时乘上\(1 + \sqrt{1 + 4 \times V(x)}\)

所以
\[ \begin {aligned} F(x)&={1^2 - \big(\sqrt{1 - 4 \times V(x)}\big)^2 \over {2 \times V(x) \times \big(1 + \sqrt{1 - 4 \times V(x)} \big)}} \\&={4 \times V(x) \over {2 \times V(x) \times \big(1 + \sqrt{1 - 4 \times V(x)}} \big)} \\&={2 \over {1 + \sqrt{1 - 4 \times V(x)}}} \end {aligned} \]

多项式求逆和多项式开根可以看我的这篇blog : 多项式的一坨东西(FFT、NTT、多项式开根、多项式求逆)

代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = 998244353LL;

const int N = 400010;

char I[8000010], *pos, *End;

inline char GetChar()
{   if(pos == End)
    {   End = (pos = I) + fread(I, 1, 8000000, stdin);
        if(pos == End) return EOF;
    }
    return *pos++;
}

inline int rd_int()
{   int x = 0, f = 1;
    char c = GetChar();
    while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = GetChar(); }
    while(c >= ‘0‘ && c <= ‘9‘) { x = x*10 + c-‘0‘; c = GetChar(); }
    return x*f;
}


int Bit;

inline LL power(LL a, LL n)
{   LL ans = 1;
    while (n)
    {   if (n & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

int rev[N];

void getReverse(int Len)
{   for (int i = 0; i < Len; i++)
        rev[i] = (rev[i>>1] >> 1) | ((i&1) * (Len>>1));
}

LL w_n[N];

void NTT(LL * a, int opt, int Len)
{   getReverse(Len);
    for (int i = 0; i < Len; i++)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (register int i = 2; i <= Len; i <<= 1)
    {   LL w_n = power(3LL, (mod-1LL) / (LL)i);
        if (opt == -1) w_n = power(w_n, mod-2);
        for (register int j = 0; j < Len; j += i)
        {   LL w = 1;
            for (register int k = 0; k < (i>>1); k++)
            {   LL x = a[j + k];
                LL y = (w * a[j + k + (i>>1)]) % mod;
                a[j + k] = (x + y) % mod;
                a[j + k + (i>>1)] = (x - y + mod) % mod;
                w = (w * w_n) % mod;
            }
        }
    }
    if (opt == -1)
    {   LL num = power(Len, mod-2);
        for (register int i = 0; i < Len; i++)
            a[i] = (a[i] * num) % mod;
    }
}

int getBit(int l)
{   Bit = 0;
    for (; (1 << Bit) <= l; Bit++);
}

inline void cpy(LL * a, LL * b, int n, int Len)
{   for (register int i = 0; i < n; i++) a[i] = b[i];
    for (register int i = n; i < Len; i++) a[i] = 0;
}

LL tmp1[N], tmp2[N];

void get_Inv(LL * a, LL * b, int l)
{   b[0] = power(a[0], mod-2);
    for (register int i = 2; i <= l; i <<= 1)
    {   int Len = i << 1;
        cpy(tmp1, a, i, Len);
        cpy(tmp2, b, i>>1, Len);
        NTT(tmp1, 1, Len);
        NTT(tmp2, 1, Len);
        for (register int j = 0; j < Len; j++)
            tmp1[j] = ((2LL*tmp2[j])%mod + mod - (((tmp2[j]*tmp2[j])%mod)*tmp1[j])%mod) % mod;
        NTT(tmp1, -1, Len);
        for (register int j = 0; j < i; j++)
            b[j] = tmp1[j];
    }
}

LL inv2;

LL tmp3[N], tmp4[N], tmp5[N];

void Sqrt(LL * a, LL * b, int l)
{   b[0] = 1;
    for (register int i = 1; i <= l; i <<= 1)
    {   int Len = i << 1;
        for (register int j = 0; j < Len; j++)
            if (j < i) tmp3[j] = (2LL * b[j]) % mod;
            else tmp3[j] = 0;
        get_Inv(tmp3, tmp4, i);
        for (register int j = i; j < Len; j++) tmp4[j] = 0;
        cpy(tmp5, a, i, Len);
        NTT(tmp4, 1, Len);
        NTT(tmp5, 1, Len);
        for (register int j = 0; j < Len; j++)
            tmp4[j] = (tmp4[j] * tmp5[j]) % mod;
        NTT(tmp4, -1, Len);
        for (register int j = 0; j < (i << 1); j++)
            b[j] = (inv2 * b[j] + tmp4[j]) % mod;
    }
}

LL a[N], b[N], ans[N];

LL v[N];

int main()
{   int n, m;
    n = rd_int(), m = rd_int();
    m++;
    for (register int i = 1; i <= n; i++)
    {   int x;
        x = rd_int();
        v[x]++;
    }
    inv2 = power(2, mod - 2);
    getBit(m);
    a[0] = 1;
    for (register int i = 1; i < m; i++)
        a[i] = (4 * (mod - v[i])) % mod;
    Sqrt(a, b, (1 << Bit));
    b[0] = (b[0] + 1) % mod;
    get_Inv(b, ans, (1 << Bit));
    for (register int i = 1; i < m; i++)
        printf("%lld\n", (ans[i] * 2LL) % mod);
    return 0;
}

【BZOJ3625】【CF438E】小朋友和二叉树

原文：https://www.cnblogs.com/2016gdgzoi509/p/8999460.html