题目要求求出有 $n (n \leq 130000)$ 个点的有标号简单连通无向图的个数，答案 $\bmod 1004535809$ $(479 \times 2^{21} + 1)$，是个质数

比如三个点的情况

题目链接：BZOJ-3456

首先可以设 $f(n)$ 表示有 $n$ 个点的有标号简单连通无向图的个数，$g(n)$ 表示有 $n$ 个点的有标号简单无向图的个数（也就是不要求连通）

$g(n)$ 是很好求的，因为 $n$ 个点，最多 $n \choose 2$ 条边，因此

\[g(n) = 2^{n \choose 2}\]

又因为一个有标号简单无向图是由很多连通分量组成的，为了避免重复计数，我们枚举点 $1$ 所在的连通块大小（其余的点随便连边，因为 $1$ 号点所在连通块已经确定，其它怎么连都不会重复）

\[g(n) = \sum_{i = 1}^{n} { {n - 1} \choose {i - 1} } f(i) g(n - i)\]

我们把 $g(n)$ 代入

\[2^{n \choose 2} = \sum_{i = 1}^{n} { {n - 1} \choose {i - 1} } f(i) 2^{ {n - i} \choose 2}\]

然后两边同时除以 $ (n - 1)! $

\[\frac{2^{n \choose 2} }{(n-1)!} = \sum_{i = 1}^{n} \frac{f(i)}{(i-1)!} \frac{2^{ {n - i} \choose 2}}{(n-i)!}\]

现在你会发现这是个卷积的形式！定义函数 $F(x), G(x), C(x)$

\[\begin{eqnarray*} F(x) &=& \sum_{n=1}^{\infty} \frac{f(n)}{(n-1)!}x^n \\ G(x) &=& \sum_{n=0}^{\infty} \frac{2^{n \choose 2}}{n!}x^n \\ C(x) &=& \sum_{n=0}^{\infty} \frac{2^{n \choose 2}}{(n-1)!}x^n \\ \end{eqnarray*}\]

可以得到

\[C(x) = F(x)G(x)\]

将其放在 $\bmod x^{n+1}$ 下

\[\begin{eqnarray*} C(x) &\equiv& F(x)G(x) \pmod{ x^{n+1} } \\F(x) &\equiv& C(x)G^{-1}(x) \pmod{ x^{n+1} } \end{eqnarray*}\]

这样求出 $G(x)$ 的逆元然后和 $C(x)$ 乘起来就可以得到 $F(x)$，也就是答案了，由于模数十分特殊，可以利用 FFT 优化（多项式求逆看这里）

不知道为什么似乎跑得好快？

#include <cstdio>
#include <algorithm>
 
using std::swap;
using std::fill;
using std::copy;
using std::reverse;
using std::reverse_copy;
 
typedef int value_t;
typedef long long calc_t;
const int MaxN = 1 << 18;
const value_t mod_base = 479, mod_exp = 21;
const value_t mod_v = (mod_base << mod_exp) + 1;
const value_t primitive_root = 3;
int epsilon_num;
value_t eps[MaxN], inv_eps[MaxN];
 
value_t dec(value_t x, value_t v) { x -= v; return x < 0 ? x + mod_v : x; }
value_t inc(value_t x, value_t v) { x += v; return x >= mod_v ? x - mod_v : x; }
value_t pow(value_t x, value_t p)
{
    value_t v = 1;
    for(; p; p >>= 1, x = (calc_t)x * x % mod_v)
        if(p & 1) v = (calc_t)x * v % mod_v;
    return v;
}
 
void init_eps(int num)
{
    epsilon_num = num;
    value_t base = pow(primitive_root, (mod_v - 1) / num);
    value_t inv_base = pow(base, mod_v - 2);
    eps[0] = inv_eps[0] = 1;
    for(int i = 1; i != num; ++i)
    {
        eps[i] = (calc_t)eps[i - 1] * base % mod_v;
        inv_eps[i] = (calc_t)inv_eps[i - 1] * inv_base % mod_v;
    }
}
 
void transform(int n, value_t *x, value_t *w = eps)
{
    for(int i = 0, j = 0; i != n; ++i)
    {
        if(i > j) swap(x[i], x[j]);
        for(int l = n >> 1; (j ^= l) < l; l >>= 1);
    }
 
    for(int i = 2; i <= n; i <<= 1)
    {
        int m = i >> 1, t = epsilon_num / i;
        for(int j = 0; j < n; j += i)
        {
            for(int p = 0, q = 0; p != m; ++p, q += t)
            {
                value_t z = (calc_t)x[j + m + p] * w[q] % mod_v;
                x[j + m + p] = dec(x[j + p], z);
                x[j + p] = inc(x[j + p], z);
            }
        }
    }
}
 
void inverse_transform(int n, value_t *x)
{
    transform(n, x, inv_eps);
    value_t inv = pow(n, mod_v - 2);
    for(int i = 0; i != n; ++i)
        x[i] = (calc_t)x[i] * inv % mod_v;
}
 
struct poly_t
{
    int deg;
    value_t x[MaxN];
    poly_t() : deg(0) { x[0] = 0; }
};
 
void polynomial_inverse(int n, const poly_t& A, poly_t& B)
{
    if(n == 1)
    {
        B.deg = 1;
        B.x[0] = pow(A.x[0], mod_v - 2);
        return;
    }
 
    static value_t X[MaxN];
    polynomial_inverse((n + 1) >> 1, A, B);
 
    int p = 1;
    for(; p < n << 1; p <<= 1);
    copy(A.x, A.x + n, X);
    fill(X + n, X + p, 0);
    transform(p, X);
 
    fill(B.x + B.deg, B.x + p, 0);
    transform(p, B.x);
 
    for(int i = 0; i != p; ++i)
        B.x[i] = (calc_t)B.x[i] * dec(2, (calc_t)X[i] * B.x[i] % mod_v) % mod_v;
    inverse_transform(p, B.x);
    B.deg = n;
}
 
poly_t A, B, C;
value_t inv[MaxN], inv_fac[MaxN], choose[MaxN];
 
int main()
{
    int n;
    std::scanf("%d", &n);
    int p = 1;
    for(; p < (n + 1) << 1; p <<= 1);
    init_eps(p);
 
    inv[1] = inv_fac[0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        if(i != 1) inv[i] = -mod_v / i * (calc_t)inv[mod_v % i] % mod_v;
        if(inv[i] < 0) inv[i] += mod_v;
        inv_fac[i] = (calc_t)inv_fac[i - 1] * inv[i] % mod_v;
    }
 
    choose[0] = choose[1] = 1;
    for(int i = 2; i <= n; ++i)
        choose[i] = pow(2, (calc_t)i * (i - 1) / 2 % (mod_v - 1));
 
    A.deg = B.deg = n + 1;
    for(int i = 0; i <= n; ++i)
        A.x[i] = (calc_t)choose[i] * inv_fac[i] % mod_v;
    for(int i = 1; i <= n; ++i)
        B.x[i] = (calc_t)choose[i] * inv_fac[i - 1] % mod_v;
    polynomial_inverse(n + 1, A, C);
    fill(C.x + C.deg, C.x + p, 0);
    transform(p, C.x);
    transform(p, B.x);
    for(int i = 0; i <= p; ++i)
        C.x[i] = (calc_t)C.x[i] * B.x[i] % mod_v;
    inverse_transform(p, C.x);
    value_t ans = (calc_t)C.x[n] * pow(inv_fac[n - 1], mod_v - 2) % mod_v;
    if(ans < 0) ans += mod_v;
    std::printf("%d\n", ans);
    return 0;
}

本文遵守 CC BY-NC 4.0 许可协议。