普通生成函数（OGF）

$$\frac{1}{1-x} = 1+x+x^2+x^3+…$$

证：等比数列，公比为 $x$。

$$\frac{1}{(1-x)^2} = 1+2x+3x^2+4x^3+…$$

证：因为

$$\frac{1}{(1-x)^2} = (\frac{1}{1-x})^2 = (1+x+x^2+x^3+…)^2$$

根据组合意义，对于 $x^k$，有 $(0,k),(1,k-1),…,(k,0)$ 共 $(k+1)$ 种组合方式，并且每一种的系数为 $1$，所以 $x^k$ 的系数为 $(k+1)$。

$$\frac{1}{1-ax} = 1+ax+a^2x^2+a^3x^3+…$$

证：等比数列，公比为 $ax$。

$$\frac{1}{(1-ax)^n} = \sum\limits_{i=0}^{\infty}C_{(n-1)+i}^{(n-1)}a^ix^i$$

证：因为

$$\frac{1}{(1-ax)^n} = (1+ax+a^2x^2+a^3x^3+…)^n$$

根据组合意义，对于 $x^k$ 而言，每个 $(1+ax+a^2x^2+a^3x^3+…)$ 都可以贡献给 $k$，而这样的式子有 $n$ 个。

所以相当于：

这是 小球放盒子 模型，$k$ 个球放入 $n$ 个盒子并且允许空盒，用隔板法即可，方案数为 $C_{(n-1)+k}^{(n-1)}$，这就是 $a^kx^k$ 的系数。

$$\frac{1}{1+x} = 1-x+x^2-x^3+…$$

等比数列，公比为 $-x$。

数列 $a$ 为：

$$a = \{0,1,4,9,16,…\}$$

那么生成函数的展开式为：

$$f(x) = x + 4x^2 + 9x^3 + 16x^4 + … = \sum\limits_{i=1}^{\infty}i^2x^i$$

在推导生成函数的封闭式时，一个非常重要的 trick 是给展开式 乘上一个 $x$。

那么乘上 $x$ 以后，相当于整个展开式向右移动了一位，对应的生成函数就是

$$xf(x) = 0 + x^2 + 4x^3 + 9x^4 + … = \sum\limits_{i=1}^{\infty}(i-1)^2x^i$$

所以两者相减，可得：

$$(1-x)f(x) = \sum\limits_{i=1}^{\infty}(i^2 - (i-1)^2)x^i = \sum\limits_{i=1}^{\infty}(2i-1)x^i$$

$$=2\sum\limits_{i=1}^{\infty}ix^i - \sum\limits_{i=1}^{\infty}x^i$$

$$=\frac{2x}{(1-x)^2} - \frac{x}{1-x}$$

• 注意到因为求和是从 $i=1$ 开始的，相当于 $i=0$ 的情况整体右移了一位，所以要乘上 $x$ 得到 $\frac{2x}{(1-x)^2}$

所以生成函数 $f(x)$ 的封闭式为：

$$f(x) = \frac{2x}{(1-x)^3} - \frac{x}{(1-x)^2} = \frac{x(x+1)}{(1-x)^3}$$

已知 $f(x)$ 的封闭式为

$$f(x) = \frac{x(x+1)}{(1-x)^3}$$

我们将其化简为上面 常用表 里面的组合，也就是 裂项：

$$f(x) = \frac{x(x+1)}{(1-x)^3} = \frac{2x}{(1-x)^3} - \frac{x}{(1-x)^2}$$

考虑第 $k$ 项的系数，注意到我们可以将分子中的 $x$ 提出来，所以 $f(x)$ 的第 $k$ 项系数 $a_k$ 就等于 $g(x) = (\frac{2}{(1-x)^3} - \frac{1}{(1-x)^2})$ 的第 $(k-1)$ 项系数 $b_{k-1}$。

$$\frac{2}{(1-x)^3} = 2\sum\limits_{i=0}^{\infty}C_{2+i}^{2}x^i, ~ \frac{x}{(1-x)^2} = \sum\limits_{i=0}^{\infty}(i+1)x^i$$

所以 $g(x)$ 的第 $(k-1)$ 项系数为：

$$b_{k-1} = [x^{k-1}]2(\sum\limits_{i=0}^{\infty}C_{2+i}^{2}x^i) - \sum\limits_{i=0}^{\infty}(i+1)x^i = 2C_{k+1}^2 - k = k^2$$

所以 $f(x)$ 的第 $k$ 项系数为 $a_k = b_{k-1} = k^2$。

于是生成函数的展开式为：

$$f(x) = \sum\limits_{i=0}^{\infty}i^2x^i = x + 4x^2 + 9x^3 + 16x^4 + …$$

注意到

$$f(x) = f_0 + f_1x^1 + f_2x^2 + f_3x^3 + …$$

$$xf(x) = 0 + f_0x^1 + f_1x^2 + f_2x^3 + …$$

$$x^2f(x) = 0 + 0+ f_0x^2 + f_1x^3 + …$$

由于 $f_i = f_{i-1} + f_{i-2}$，所以：

$$f(x)(1-x-x^2) = f_0 + (f_1-f_0)x^1 = x$$

所以 $$f(x) = \frac{x}{1-x-x^2}$$

$$f(x) = \frac{x}{1-x-x^2}$$

我们希望将它转为表格中存在的形式，所以我们设：

$$(1-ax)(1-bx) = 1-x-x^2$$

可得 $a = \frac{1 + \sqrt 5}{2}, b = \frac{1 - \sqrt 5}{2}$

设

$$g(x) = \frac{f(x)}{x} = \frac{1}{(1-ax)(1-bx)}$$

那么要求 $f(x)$ 的第 $n$ 项系数，只要求 $g(x)$ 的第 $(n-1)$ 项系数即可。

因为

$$g(x) = \frac{1}{(1-ax)(1-bx)}$$ $$= \sum\limits_{i=0}^{\infty}a^ix^i * \sum\limits_{j=0}^{\infty}b^jx^j$$ $$= (1+ax+a^2x^2+a^3x^3+…) * (1+bx+b^2x^2+b^3x^3+…)$$

这是个卷积，那么 $g(x)$ 的第 $(n-1)$ 项系数为：

$$[x^{n-1}]g(x) = \sum\limits_{k=0}^{n-1}a^{k}b^{n-1-k}$$

$$=b^{n-1}\sum\limits_{k=0}^{n-1}a^{k}b^{-k}$$

$$=b^{n-1}\sum\limits_{k=0}^{n-1}(\frac{a}{b})^k$$

右边就是个等比数列求和了，公比为 $\frac{a}{b}$，最后可得

$$[x^n]f(x) = [x^{n-1}]g(x) = \frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n)$$

那么求出了 $f(x)$ 的通项公式，展开式也就可以写出来了。

看到 $\sum\limits_{j=1}^if_{i-j}g_j$ 就想到卷积，也就是多项式乘法。

那么令

$$f(x) = f_0 + f_1x^1 + f_x2x^2 + … + f_{n-1}x^{n-1}$$

$$g(x) = g_0 + g_1x^1 + g_x2x^2 + … + g_{n-1}x^{n-1}$$

$$h(x) = f(x)g(x)$$

则有：

$$[x^n]h(x) = \sum\limits_{i=0}^nf_ig_{n-i}$$

发现和 $f_n = \sum\limits_{j=1}^nf_{n-j}g_j$ 就差一个 $j=0$ 的情况（多了一个 $g_0f_n$），那么我们直接令 $g_0 = 0$ 就没问题了。

这样的话，当 $n=0$ 时，$h_0 = 0$，其他时候 $h_n = f_n$。

所以：

$$f(x)g(x) = h(x) = 0 + f_1x^1 + f_x2x^2 + … + f_{n-1}x^{n-1} = f(x) - f_0 = f(x) - 1$$

得到

$$f(x)(1-g(x)) = 1$$

$$f(x) = \frac{1}{1-g(x)}$$

多项式求逆即可。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = (1<<22) + 5;
// 板子省略
ll f[maxn], g[maxn], invG[maxn];
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n-1; i++) cin >> g[i];
    for (int i = 1; i <= n-1; i++) g[i] = (-g[i] + mod) % mod;
    g[0] = 1;
    poly_inverse(g, invG, n);
    for (int i = 0; i < n; i++) {
        cout << (invG[i]) % mod << " ";
    }
    cout << endl;    
}

小tips：计数问题可以想想 dp 怎么做。

设 $f_n$ 为 $n$ 个节点的 简单（无重边无自环）有标号无向 连通 图数目。

设 $g_n$ 为 $n$ 个节点的 简单（无重边无自环）有标号无向图数目。（区别在于不需要连通）

发现在一个完全图中有 $C_n^2$ 条边，每条边可以选或者不选，那么

$$g_n = 2^{C_n^2}$$

我们想要用另外一种方式表示 $g_n$，可以枚举 节点 $1$ 所在的联通块的大小：

1. 节点 $1$ 所在联通块大小为 $1$ 时，方案数为：$f_1g_{n-1}$
2. 节点 $1$ 所在联通块大小为 $2$ 时，方案数为：$C_{n-1}^{1}f_2g_{n-2}$
3. 节点 $1$ 所在联通块大小为 $k$ 时，方案数为：$C_{n-1}^{k-1}f_kg_{n-k}$

所以联通块大小 $1$ 枚举到 $n$，有：

$$g_n = \sum\limits_{i=1}^n C_{n-1}^{i-1}f_ig_{n-i}$$

看到 $f_ig_{n-i}$ 的形式马上想到 卷积，也就是 多项式乘法。

但是有一个 $C_{n-1}^{i-1}$，我们把它拆开即可：

$$g_n = \sum\limits_{i=1}^n C_{n-1}^{i-1}f_ig_{n-i}$$

$$g_n = (n-1)!\sum\limits_{i=1}^n\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}$$

令

$$F_i = \frac{f_i}{(i-1)!}, G_i = \frac{g_i}{i!}$$

则有：

$$\frac{g_n}{(n-1)!} = \sum\limits_{i=1}^nF_iG_{n-i}$$

令

$$F(x) = 0 + F_1x + F_2x^2 + … + F_{n}x^n$$

$$G(x) = G_0 + G_1x + G_2x^2 + … + G_{n}x^n$$

则可以发现，（注意 $F(x)$ 的常数项为 $0$）：

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

注意到 $\frac{1}{(n-1)!}$ 是不可以提到外面去的，因为它与 $n$ 有关。

定义

$$H_n = \frac{g_n}{(n-1)!}, H_0 = 0$$

• $H_0 = 0$ 是因为：如果我们代入 $n=0$ 进 $[x^n]\frac{g(x)}{(n-1)!} = [x^n]F(x)G(x)$，会发现右边为 $0$，所以 $H_0 = 0$。

则有：

$$[x^n]H(x) = [x^n]F(x)G(x)$$

注意到左右两个多项式的 $n$ 次项系数对于任何 $n$ 都相等，所以有

$$H(x) = F(x)G(x)$$

$$F(x) = \frac{H(x)}{G(x)}$$

由于 $H(x), G(x)$ 均已知，多项式求逆即可求出 $F(x)$，在每一项系数上乘以 $(n-1)!$ 即可得到 $f(x)$。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1004535809;
const int maxn = (1<<22) + 5;
// 多项式板子部分省略

ll f[maxn], g[maxn], G[maxn], invG[maxn], fac[maxn], invfac[maxn], h[maxn];
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}


int main() {
    int n; cin >> n;
    g[0] = 1;
    for (ll i = 1; i <= n; i++) {
        g[i] = qpow(2, i * (i-1) / 2);
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * (ll)i % mod;
    invfac[n] = qpow(fac[n], mod-2);
    for (int i = n-1; i >= 0; i--) invfac[i] = invfac[i+1] * (ll)(i+1) % mod;

    h[0] = 0;
    for (int i = 0; i <= n; i++) G[i] = g[i] * invfac[i] % mod;
    for (int i = 1; i <= n; i++) h[i] = g[i] * invfac[i-1] % mod;
    poly_inverse(G, invG, n+1);
    poly_multiply(h, n+1, invG, n+1, f);

    f[n] = f[n] * fac[n-1] % mod;
    cout << f[n] << endl;
}

首先用 dp 的思路：

设 $f_n$ 为权值和为 $n$ 的二叉树个数（根的值 尚未确定），设 $g_n$ 为权值和为 $n$ 的二叉树个数（根的值 已经确定）。

则我们可以得出：

$$f_n = \sum\limits_{i=1}^n g_{n-c_i}$$

$$g_n = \sum\limits_{i=0}^n f_if_{n-i}$$

解释：

对于第一个式子，我们枚举根的值即可。

对于第二个式子，由于根的值已经确定，所以只需要枚举左右子树的权值和即可。

我们看到 $g_n = \sum\limits_{i=0}^n f_if_{n-i}$，发现这就是个卷积，所以有

$$g(x) = f(x)^2$$

但第一个式子怎么办呢？这是个加法，无法表示为卷积？

注意到本题中所有的权值 $\leq 10^5$，我们不如定义 $h_i$ 为：

$$h_i = \begin{cases} 1 ~~~~ \text{if } i \in \{c_1, c_2, …, c_n\} \\
0 ~~~~ \text{if } i \notin \{c_1, c_2, …, c_n\} \end{cases}$$

则我们可以将 $f_n = \sum\limits_{i=1}^n g_{n-c_i}$ 转化为：

$$f_n = \sum\limits_{i=1}^nh_ig_{n-i}$$

这就又是个卷积了，代入 $n=0$ 可以发现：因为 $f_0 = g_0 = 1, h_0 = 0$，所以

$$f(x) = h(x)g(x) + 1 = h(x)f(x)^2 + 1$$

所以：

$$h(x)f(x)^2 - f(x) + 1 = 0$$

利用公式 $x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$ 有：

$$f(x) = \frac{1 \pm \sqrt{1-4h(x)}}{2h(x)}$$

有个问题，$h(x)$ 的常数项 $h(0) = 0$ 没法求逆？（注意到求逆的本质是 $h(x) * h^{-1}(x) = 1$）

没关系，没法求逆就乘到左边去，得到：

$$2f(x)h(x) = 1 \pm \sqrt{1-4h(x)}$$

代入 $x = 0$，由 $h(0) = 0$ 可以得到右边只能取 负号。

所以再把 $h(x)$ 除回去，得到：

$$f(x) = \frac{1 - \sqrt{1-4h(x)}}{2h(x)}$$

上下同乘 $(1 + \sqrt{1-4h(x)})$ 得到：

$$f(x) = \frac{2}{1 + \sqrt{1-4h(x)}}$$

多项式求逆求出 $f(x)$ 即可。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = (1<<21) + 5;

int n,m;
ll h[maxn], H[maxn];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int c; cin >> c;
        h[c] = 1;
    }
    for (int i = 1; i <= 1e5; i++) {
        h[i] = 4LL * h[i] % mod;
        h[i] = (-h[i] + mod) % mod;
    }
    h[0] = (h[0] + 1) % mod;
    poly_sqrt(h, H, 1e5+1);
    H[0] = (H[0] + 1) % mod;
    memset(h, 0, sizeof(h));
    poly_inverse(H, h, 1e5+1);
    for (int i = 1; i <= m; i++) {
        cout << h[i] * 2LL % mod << "\n";
    }
}

我们发现这个 $\sum$ 和 $\prod$ 的顺序其实可以调换的。

所以我们枚举一下第一个元素 $a_1$，设 $f_n$ 为我们所求的值，问题就转化为：

$$f_n = \sum\limits_{j=1}^nF_j*f_{n-j}$$

其中，$f_0 = 1$。

所以设

$$G(x) = F(x)f(x)$$

$$G(0) = F(0)f(0) = 0$$

所以有

$$f(x) = G(x) + 1 = F(x)f(x) + 1$$

得出

$$f(x) = \frac{1}{1-F(x)}$$

斐波那契数列的生成函数为（不记得了就手推一下）：$$F(x) = \frac{x}{1-x-x^2}$$

所以得到：

$$f(x) = \frac{1-x-x^2}{1-2x-x^2} = 1-\frac{x}{x^2+2x-1}$$

我们发现这个常数项 $1$ 对我们的 $n$ 次项系数 $f_n$ 并没有任何影响，所以可以直接忽略。

现在我们需要裂项了，转化为表里面的形式：

$$f(x) = \frac{-x}{x^2+2x-1} = \frac{c}{1-ax} + \frac{d}{1-bx}$$

解方程就可以得到

$$b = -1\pm \sqrt 2, a = -1 \mp \sqrt 2$$

发现随便取哪个符号都一样（毕竟 $a,b$ 本就是对称的），所以有：

$$b = 1 + \sqrt 2, a = 1 - \sqrt 2, c = -\frac{1}{2\sqrt 2}, d = \frac{1}{2\sqrt 2}$$

所以

$$f(x) = \frac{c}{1-ax} + \frac{d}{1-bx}$$

$f(x)$ 的第 $n$ 次项系数为：

$$[x^n]f(x) = -\frac{1}{2 \sqrt 2}(a^n - b^n) = \frac{1}{2\sqrt 2}[(1+\sqrt 2)^n - (1-\sqrt 2)^n]$$

最后的问题就是如何求 $(1+\sqrt 2)^n - (1-\sqrt 2)^n$ ？

我们需要先知道 $\sqrt 2$ 在 $\text{mod }10^9 + 7$ 意义下的值，可以利用二次剩余解决。

然后对于 $n$，我们发现它出现在指数位置，而我们由费马小定理知道 $\forall a, a^{P-1} \equiv 1 (\text{mod } P)$

所以，我们只要将 $n$ 取一个 $n = n(\text{mod } (P-1))$ 即可。

#include <bits/stdc++.h>
using namespace std;
const ll mod = 1e9+7;
const int maxn = 1e5+7;

// 求 sqrt(a) 在 mod P 下的值
// 调用 solve(a, P, r1, r2)
// 若有解，r1, r2 分别为两个解，其中 r1 小，r2 大
// 若无解，r1 == -1
namespace Quadratic_residue {
    ll qpow(ll a, ll b, ll P) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }

    bool check_if_residue(ll x, ll P) {
        return qpow(x, (P - 1) >> 1, P) == 1;
    }

    void solve(ll a, ll P, ll& r1, ll& r2) {
        if (a <= 1) {
            r1 = a, r2 = P - a; return;
        }
        if (!check_if_residue(a, P)) {
            r1 = -1; return;
        }
        ll x;
        while (1) {
            x=1ll*rand()*rand()%P;
            if (qpow((x*x-a+P)%P,(P-1)/2, P)!=1) break;
        }
        ll w=(x*x-a+P)%P;
        pll res = {1,0}, t = {x,1};
        auto Mul=[&](pll a,pll b){ // 复数乘法
            ll x=(1ll*a.first*b.first+1ll*a.second*b.second%P*w)%P;
            ll y=(1ll*a.first*b.second+1ll*a.second*b.first)%P;
            return make_pair(x,y);
        };
        ll d=(P+1)/2;
        while (d) {
            if(d&1) res=Mul(res,t);
            t=Mul(t,t);
            d>>=1;
        }
        ll r = (res.first % P + P) % P;
        r1 = min(r, (P - r) % P);
        r2 = max(r, (P - r) % P);
    }
};

ll s2, _;  //sqrt(2)
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll a) {
    return qpow(a, mod-2);
}

ll readBigint() {
    string s; cin >> s;
    ll res = 0;
    for (int i = 0; i < s.size(); i++) {
        res = res * 10 % (mod - 1);
        res = (res + (s[i] - '0')) % (mod - 1);
    }
    return res;
}

int main() {
    ll n = readBigint();
    Quadratic_residue::solve(2, mod, s2, _);

    ll ans = qpow((1LL + s2) % mod, n) - qpow((1LL - s2 + mod) % mod, n);
    ans = (ans + mod) % mod;
    ans = ans * inv(2LL * s2 % mod) % mod;
    cout << ans << "\n";
}