luoguP7364 有标号二分图计数

生成函数 + NTT

有标号二分图计数

思路

看见要把 $1 \sim 10^5$ 都算出来，考虑 GF ，设答案（有标号二分图计数）的 GF 为 $G(x)$

发现这并不好做，因为不一定联通两个联通块的信息不好组合，考虑 EGF 部分与整体 $\exp$ 的关系，设 $G(x)$ 是一个 EGF ，再设有标号二分联通图计数的 EGF 为 $F(x)$ ，那么显然有 $\exp(F) = G$

发现 $F$ 也写不出式子，考虑啥写得出来：二分图的染色，发现就是 $h_n = \sum_{i = 0}^{n} \binom{n}{i} 2^{i(n - i)}$ 理解很简单，选 $i$ 个点染黑色，其它染白色，我们设 $h$ 的EGF 为 $H(x)$ ，现在换一种方式理解，给每个二分图的连通图的一个点钦定一个颜色，则该连通图所有点颜色确定，于是：
$$
H(x) = \sum \frac{2^{i} F^i(x)}{i!} = e^{2F(x)}
$$
发现 $G(x) = \sqrt{H(x)}$ ，现在要快速求 $H(x)$ ，考虑到：
$$
\begin{aligned}
& h_n = \sum_{i = 0}^{n} \binom{n}{i} 2^{i(n - i)} \\
& h_n = \sum_{i = 0}^n \frac{n!}{i!(n - i)!} 2^{\frac{n(n - 1) - i(i - 1) - (n - i)(n - i - 1)}{2}} \\
& h_n = \sum_{i = 0}^n 2^{\frac{n(n - 1)}{2}} \frac{n!}{i!(n - i)!} \frac{1}{2^{\frac{i(i - 1)}{2}}} \frac{1}{2^{\frac{(n - i)(n - i - 1)}{2}}} \\
& h_n = n!2^{\frac{n(n - 1)}{2}} \sum_{i = 0}^n \frac{1}{i!2^{\frac{i(i - 1)}{2}}} \frac{1}{(n - i)!2^{\frac{(n - i)(n - i - 1)}{2}}} \\
& h_n = n!2^{\binom{n}{2}} \sum_{i = 0}^n \frac{1}{i!2^{\binom{i}{2}}} \frac{1}{(n - i)!2^{\binom{n - i}{2}}} \\
\end{aligned}
$$
这个东西的组合意义是：本来有 $2^{\binom{n}{2}}$ 条边，但两个联通块内的边 $2^{\binom{i}{2}}, 2^{\binom{n - i}{2}}$ 不算

有了上式， $H(x)$ 显然可以卷积得到，再做多项式开根即得 $G(x)$ ，发现 $[x^0]H(x) = 1$ 所以不必写二次剩余

代码

#include <bits/stdc++.h>
using LL = long long;
const int P = 998244353, G = 3, N = 1e6 + 100, L = 1e5 + 1;
int qpow(int x, int y = P - 2)
{
    int res = 1;
    for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
    return res;
}
void adj(int &x){ x += (x >> 31) & P; }
namespace Poly
{
    int r[N];
    void rdy(int &bit, int &tot, int len){ for (tot = 1, bit = 0; tot < len + 1; tot <<= 1, ++bit); }
    void get_r(int bit, int tot){ for (int i = 0; i < tot; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1)); }
    void ntt(int *x, int tot, int op)
    {
        static int gn[N];
        for (int i = 1; i < tot; ++i) if (i < r[i]) std::swap(x[i], x[r[i]]);
        for (int mid = 1; mid < tot; mid <<= 1)
        {
            int g0 = qpow(G, (P - 1) / (mid << 1));
            if (op == -1) g0 = qpow(g0);
            gn[0] = 1;
            for (int i = 1; i < mid; ++i) gn[i] = LL(gn[i - 1]) * g0 % P;
            for (int i = 0; i < tot; i += (mid << 1))
                for (int *x1 = x + i, *x2 = x1 + mid, *ed = x2, *g = gn; x1 != ed; ++x1, ++x2, ++g)
                {
                    int p = *x1, q = LL(*x2) * *g % P;
                    adj(*x1 = p + q - P), adj(*x2 = p - q);
                }
        }
        if (op == 1) return ;
        int t = qpow(tot);
        for (int i = 0; i < tot; ++i) x[i] = LL(x[i]) * t % P;
    }
    void inv(int *x, int *y, int len)
    {
        if (len == 1) return void(y[0] = qpow(x[0]));
        inv(x, y, (len + 1) >> 1);
        int bit, tot;
        static int t[N];
        rdy(bit, tot, len << 1), get_r(bit, tot);
        std::fill(y + ((len + 1) >> 1), y + tot, 0);
        std::copy(x, x + len, t);
        std::fill(t + len, t + tot, 0);
        ntt(t, tot, 1), ntt(y, tot, 1);
        for (int i = 0, tt; i < tot; ++i)
        {
            adj(tt = 2 - LL(t[i]) * y[i] % P);
            y[i] = LL(tt) * y[i] % P;
        }
        ntt(y, tot, -1);
        std::fill(y + len, y + tot, 0);
    }
    void dif(int *x, int *y, int len)
    {
        for (int i = 1; i < len; ++i) y[i - 1] = LL(x[i]) * i % P;
        y[len - 1] = 0;
    }
    void inte(int *x, int *y, int len)
    {
        for (int i = 1; i < len; ++i) y[i] = LL(x[i - 1]) * qpow(i) % P;
        y[0] = 0;
    }
    void ln(int *x, int *y, int len)
    {
        static int a[N], b[N];
        dif(x, a, len);
        inv(x, b, len);
        int bit, tot;
        rdy(bit, tot, len << 1), get_r(bit, tot);
        std::fill(a + len, a + tot, 0);
        std::fill(b + len, b + tot, 0);
        ntt(a, tot, 1), ntt(b, tot, 1);
        for (int i = 0; i < tot; ++i) a[i] = LL(a[i]) * b[i] % P;
        ntt(a, tot, -1);
        std::fill(a + len, a + tot, 0);
        inte(a, y, len);
        std::fill(y + len, y + tot, 0);
    }
    void exp(int *x, int *y, int len)
    {
        if (len == 1) return void(y[0] = 1);
        exp(x, y, (len + 1) >> 1);
        int bit, tot;
        static int t[N];
        rdy(bit, tot, len << 1);
        std::fill(t, t + tot, 0);
        ln(y, t, len);
        get_r(bit, tot);
        adj(t[0] = x[0] + 1 - t[0]);
        for (int i = 1; i < len; ++i) adj(t[i] = x[i] - t[i]);
        std::fill(t + len, t + tot, 0);
        ntt(t, tot, 1), ntt(y, tot, 1);
        for (int i = 0; i < tot; ++i) y[i] = LL(y[i]) * t[i] % P;
        ntt(y, tot, -1);
        std::fill(y + len, y + tot, 0);

    }
    void sqrt(int *x, int *y, int len)
    {
        static int t[N];
        ln(x, t, len);
        for (int i = 0; i < len; ++i) t[i] = LL((P + 1) >> 1) * t[i] % P;
        exp(t, y, len); 
    }
    void pow2(int *x, int *y, int len)
    {
        int bit, tot;
        rdy(bit, tot, len << 1), get_r(bit, tot);
        ntt(x, tot, 1);
        for (int i = 0; i < tot; ++i) y[i] = LL(x[i]) * x[i] % P;
        ntt(y, tot, -1);
        std::fill(y + len, y + tot, 0);
    }
}
int h[N], a[N], g[N];
int fac[N], ifac[N];
int calc(int x){ return qpow(2, x * LL(x - 1) / 2 % (P - 1)); }
int main()
{
    fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) fac[i] = LL(fac[i - 1]) * i % P;
    ifac[N - 1] = qpow(fac[N - 1]);
    for (int i = N - 2; i > 1; --i) ifac[i] = LL(i + 1) * ifac[i + 1] % P;
    for (int i = 0; i < L; ++i) a[i] = LL(ifac[i]) * qpow(calc(i)) % P;
    Poly::pow2(a, h, L);
    for (int i = 0; i < L; ++i) h[i] = LL(h[i]) * calc(i) % P;
    Poly::sqrt(h, g, L);
    for (int i = 1; i < L; ++i) printf("%lld\n", LL(g[i]) * fac[i] % P);
    return 0;
}