BZOJ3684 大朋友和多叉树

BZOJ3684 大朋友和多叉树

题目地址

首先考虑一下如果进行 $\tt Dp$ 的话需要如何进行转移。

• 考虑单独增加一个节点。

• 考虑通过题目给出的一个度数进行合并。

但是发现转移的话可能会产生一个环，那么我们就尝试使用$\tt\color{red}\text{生成函数}$，设 $F(x)$ 表示最终答案的生成函数。

那么我们根据之前的转移就可以得到方程：

$$
F(x) = x + \sum_{i \in Deg} F^i(x)
$$

我们考虑移项得到 $F(x) - \sum_{i \in Deg} F^i(x) = x$ 我们注意到这个最后这个 $x$ 貌似可以进行拉格朗日反演。

设 $G(x) = x - \sum_{i \in Deg} x^i$ 那么我们就有 $G(F(x)) = x$。带入反演的式子得到：

$$
[x^n]F(x) = \frac{1}{n}[x^{-1}]\frac{1}{G^n(x)}
$$

那么问题来了我们现在多项式能做是表示整式，显然这个 $G(x)$ 是没有逆元的。

因为 $G(0) = 0$。

那么这个就一定是一个分式。我们考虑将其用整式表示出来，不妨设其前缀 $0$ 的个数为 $d$ ：

$$
\begin{aligned}
\frac{1}{G(x)} &= \frac{1}{\frac{G(x)}{x^d}} \times \frac{1}{x^d}
\end{aligned}
$$

那么左边的部分显然是有逆元的，我们对比一下两个式子：

$$
\frac{1}{G^n(x)}\\
(\frac{x^d}{G(x)})^n
$$

显然下面的式子本质上就是向右平移了 $dn$ 个 $x$ 那么我们的答案也要相应的偏移 $dn$。也就是有如下式子：

$$
[x^{-1}] \frac{1}{G^n(x)} = [x^{dn - 1}] (\frac{x^d}{G(x)})^n
$$

那么这题就做完了，我们总结一下式子：

$$
[x^n] F(x) = \frac{1}{n}[x^{dn - 1}] (\frac{1}{\frac{G(x)}{x^d}}) ^ n
$$

实现的时候先将 $G(x)$ 平移记录平移值即可。

#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;

const int maxn = 4e5 + 5;
const int mod = 950009857;

extern void getrev(int);
extern void Deri(int*, int);
extern void reward(int *, int);
extern int ksm(int, int);
extern void NTT(int, int);
extern void Inv(const int*, int*, int);
extern void Ln(const int*, int*, int);
extern void Mul(const int*, const int*, int*, int, int, int);
extern void Sqrt(const int*, int*, int);
extern void init(int);
extern void Exp(const int*, int*, int);
extern void Ksm(const int*, int*, int, int, int);

int S, M, n, m, m1;

int lim, len, rev[maxn];

int G[maxn], F[maxn], d[maxn];
char str[maxn];

signed main() {
    init(18);
    int i, j;
    r1(S, M);
    d[0] = 1;
    for(i = 1; i <= M; ++ i) {
        int s; r1(s); d[s - 1] = mod - 1;
    }
    Inv(d, F, S);
//    for(i = 0; i < S; ++ i) printf("%d ", d[i]);
//    puts("");
    Ksm(F, G, S, S, S);
    int ans = 1ll * G[S - 1] * ksm(S, mod - 2) % mod;
    printf("%d\n", ans);
    return 0;
}

int inv[maxn], wn[2][20][maxn];

const int G1 = 7, invG1 = ksm(7, mod - 2);

void init(int up) {
    for(int t = 1; t <= up; ++ t) {
        int buf0 = ksm(G1, (mod - 1) / (1 << t));
        int buf1 = ksm(invG1, (mod - 1) / (1 << t));
        wn[0][t][0] = wn[1][t][0] = 1;
        for(int k = 1; k < (1 << t); ++ k) {
            wn[0][t][k] = 1ll * wn[0][t][k - 1] * buf0 % mod;
            wn[1][t][k] = 1ll * wn[1][t][k - 1] * buf1 % mod;
        }
    }
    for(int t = 1; t <= (1 << up); ++ t) inv[t] = ksm(t, mod - 2);
}

void getrev(int x) {
    lim = 1, len = 0;
    while(lim <= x) lim <<= 1, ++ len;
    for(int i = 0; i < lim; ++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
}

int ksm(int x,int mi) {
    int res(1);
    while(mi) {
        if(mi & 1) res = 1ll * res * x % mod;
        mi >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}

void NTT(int *A, int opt = 1) {
    for(int i = 0; i < lim; ++ i) if(i < rev[i]) swap(A[i], A[rev[i]]);
    for(int mid = 1, ts = 1; mid < lim; mid <<= 1, ++ ts) {
        for(int j = 0, c = (mid << 1); j < lim; j += c) {
            const int *w1 = wn[opt == 1 ? 0 : 1][ts];
            for(int k = 0; k < mid; ++ k) {
                int x = A[j + k], y = 1ll * A[j + k + mid] * w1[k] % mod;
                A[j + k] = (x + y) % mod;
                A[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if(opt != 1) {
        int z = inv[lim];
        for(int i = 0; i < lim; ++ i) A[i] = 1ll * A[i] * z % mod;
    }
}

void Inv(const int *F, int *G, int x) { // ПоКэ
    if(x == 1) return G[0] = ksm(F[0], mod - 2), void();
    Inv(F, G, (x + 1) >> 1);
    static int tmpf[maxn];
    getrev(x << 1);
    memset(tmpf, 0, lim * 4);
    for(int i = 0; i < x; ++ i) tmpf[i] = F[i];
    NTT(tmpf), NTT(G);
    for(int i = 0; i < lim; ++ i) G[i] = 1ll * G[i] * (2 - 1ll * tmpf[i] * G[i] % mod + mod) % mod;
    NTT(G, -1);
    for(int i = x; i < lim; ++ i) G[i] = 0;
}

void Deri(int *F, int n) {
    for(int i = 1; i < n; ++ i) F[i - 1] = 1ll * F[i] * i % mod;
    F[n - 1] = 0;
}

void reward(int *F,int n) {
    for(int i = n - 2; i >= 0; -- i) F[i + 1] = 1ll * F[i] * ksm(i + 1, mod - 2) % mod;
    F[0] = 0;
}

void Ln(const int *F,int *G,int n) {
    memset(G, 0, n * 4);
    Inv(F, G, n);
    getrev(n << 1);
    static int tmpf[maxn];
    for(int i = 0; i < n; ++ i) tmpf[i] = F[i];
    fill(tmpf + n, tmpf + lim, 0);
    Deri(tmpf, n);
    NTT(tmpf), NTT(G);
    for(int i = 0; i < lim; ++ i) G[i] = 1ll * G[i] * tmpf[i] % mod;
    NTT(G, -1);
    reward(G, n);
}

int tmpG[maxn];

const int inv2 = ksm(2, mod - 2);

void Mul(const int *A,const int *B,int *ans,int n,int m, int opt = 1) {
    static int s1[maxn], s2[maxn];
    getrev(max(n, m) << 1);
    int limpr = lim;
    memset(s1, 0, 4 * lim), memcpy(s1, A, n * 4), NTT(s1);
    memset(s2, 0, 4 * lim), memcpy(s2, B, m * 4), NTT(s2);
    for(int i = 0; i < lim; ++ i) ans[i] = 1ll * s1[i] * s2[i] % mod;
    NTT(ans, -1);
    if(opt != 1) getrev(limpr);
}

void Sqrt(const int *F, int *G,int n) {
    if(n == 1) return G[0] = 1, void();
    Sqrt(F, G, (n + 1) >> 1);
    memset(tmpG, 0, n * 4);
    Inv(G, tmpG, n);
    Mul(F, tmpG, tmpG, n, n);
    for(int i = 0; i < n; ++ i) G[i] = 1ll * inv2 * (tmpG[i] + G[i]) % mod;
}

void Exp(const int *F, int *G,int n) {
    if(n == 1) return G[0] = 1, void();
    static int tmp[maxn];
    Exp(F, G, (n + 1) >> 1);
    getrev(n << 1);
    memset(tmp, 0, lim * 4);
    Ln(G, tmp, n);
    for(int i = 0; i < n; ++ i) tmp[i] = (F[i] - tmp[i] + mod) % mod;
    tmp[0] = (tmp[0] + 1) % mod;
    Mul(G, tmp, G, n, n);
    for(int i = n; i < lim; ++ i) G[i] = 0;
}

void Ksm(const int *F, int *G,int n,int miyuan,int mi) {
    memset(G, 0, 4 * n);
    if(mi == 0) return G[0] = 1, void();
    static int tmpf[maxn];
    memset(tmpf, 0, n * 4);
    Ln(F, tmpf, n);
    for(int i = 0; i < n; ++ i) tmpf[i] = 1ll * tmpf[i] * miyuan % mod;
    Exp(tmpf, G, n);
}

}

signed main() { return Legendgod::main(), 0; }