BZOJ-3456. 城市规划

Posted by miskcoo on May 28, 2015

题目要求求出有 $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 优化(多项式求逆看这里

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#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;
}