Early's Blog

Hello, World!

0%

「集训队作业 2013」城市规划

发表于 分类于
本文字数： 3.8k

题目链接

题意

求 nn 个点的简单有标号无向连通图个数。

思路

前置知识：由 ii 个点组成的无向图个数为 2C(i,2)2^{C(i,2)}（记为 gig_i）。

设 fif_i 为 ii 个点的简单有标号无向连通图个数，根据容斥，得：

fi=gi−∑j=1i−1fj⋅C(i−1,j−1)⋅gi−jf_i=g_i-\sum_{j=1}^{i-1}f_j\cdot C(i-1,j-1)\cdot g_{i-j}

即枚举 11 号点所在联通块大小，其它点随便选。

开始推式子：

fi=gi−∑j=1i−1fj⋅C(i−1,j−1)⋅gi−jfi=gi−∑j=1i−1fj⋅gi−j⋅(i−1)!(j−1)!⋅(i−j)!fi(i−1)!=gi(i−1)!−∑j=1i−1fj(j−1)!⋅gi−j(i−j)!fi(i−1)!=i⋅gii!−∑j=1i−1fj(j−1)!⋅gi−j(i−j)!\begin{aligned} f_i&=g_i-\sum_{j=1}^{i-1}f_j\cdot C(i-1,j-1)\cdot g_{i-j}\\ f_i&=g_i-\sum_{j=1}^{i-1}f_j\cdot g_{i-j}\cdot\frac{(i-1)!}{(j-1)!\cdot(i-j)!}\\ \frac{f_i}{(i-1)!}&=\frac{g_i}{(i-1)!}-\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\cdot\frac{g_{i-j}}{(i-j)!}\\ \frac{f_i}{(i-1)!}&=i\cdot\frac{g_i}{i!}-\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\cdot\frac{g_{i-j}}{(i-j)!} \end{aligned}

设：

F(i)=fi(i−1)!G(i)=gii!H(i)=∑j=1i−1F(j)⋅G(i−j)\begin{aligned} F(i)&=\frac{f_i}{(i-1)!}\\ G(i)&=\frac{g_i}{i!}\\ H(i)&=\sum_{j=1}^{i-1}F(j)\cdot G(i-j) \end{aligned}

则：

G(i)=2C(i,2)i!F(i)=i⋅G(i)−H(i)H(i)=∑j=1i−1F(j)⋅G(i−j)\begin{aligned} G(i)&=\frac{2^{C(i,2)}}{i!}\\ F(i)&=i\cdot G(i)-H(i)\\ H(i)&=\sum_{j=1}^{i-1}F(j)\cdot G(i-j) \end{aligned}

这是一个标准的分治 FFT，直接用 O(nlog⁡2n)O(n\log^2n) 的时间复杂度解决。

实现

按式子求就行。

把 F(0)F(0) 和 G(0)G(0) 设为 00，这样 H(i)H(i) 就可以变成 ∑j=0iF(j)⋅G(i−j)\sum_{j=0}^{i}F(j)\cdot G(i-j)，更好求一些。

代码

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
#include<cstdio>
using namespace std;
const int N=1<<18,G=3,mod=1004535809,invG=(mod+1)/G;
int n,fac[N],invf[N];
int rev[N],f[N],g[N],h[N];
inline void swap(int &x,int &y)
{
    x^=y^=x^=y;
    return;
}
int pow(int x,int times)
{
    int ret=1;
    while(times) {
        if(times&1) {
            ret=1ll*ret*x%mod;
        }
        times>>=1,x=1ll*x*x%mod;
    }
    return ret;
}
void init_pow()
{
    fac[0]=1;
    for(int i=1;i<=n;++i) {
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    invf[n]=pow(fac[n],mod-2);
    for(int i=n;i;--i) {
        invf[i-1]=1ll*invf[i]*i%mod;
    }
    return;
}
void init(int len)
{
    for(int i=0;i<len;++i) {
        rev[i]=(rev[i>>1]>>1)|(i&1?len>>1:0);
    }
    return;
}
void ntt(int f[],int n,bool flag)
{
    for(int i=0;i<n;++i) {
        if(i<rev[i]) {
            swap(f[i],f[rev[i]]);
        }
    }
    for(int len=2,k=1;len<=n;len<<=1,k<<=1) {
        for(int i=0,uni=pow(flag?G:invG,(mod-1)/len);i<n;i+=len) {
            for(int j=i,w=1;j<i+k;++j,w=1ll*w*uni%mod) {
                int tem=1ll*w*f[j+k]%mod;
                f[j+k]=(f[j]-tem)%mod,f[j]=(f[j]+tem)%mod;
            }
        }
    }
    return;
}
void cdq(int l,int r)
{
    static int temf[N],temg[N];
    if(r-l==1) {
        f[l]=(1ll*l*g[l]-h[l])%mod;
        return;
    }
    int mid=(l+r)/2,siz=r-l;
    cdq(l,mid);
    int len;
    for(len=1;len<siz;len<<=1);
    init(len);
    for(int i=l;i<mid;++i) {
        temf[i-l]=f[i];
    }
    for(int i=mid-l;i<len;++i) {
        temf[i]=0;
    }
    for(int i=0;i<siz;++i) {
        temg[i]=g[i];
    }
    for(int i=siz;i<len;++i) {
        temg[i]=0;
    }
    ntt(temf,len,true),ntt(temg,len,true);
    for(int i=0;i<len;++i) {
        temf[i]=1ll*temf[i]*temg[i]%mod;
    }
    ntt(temf,len,false);
    for(int i=0,invlen=pow(len,mod-2);i<len;++i) {
        temf[i]=1ll*temf[i]*invlen%mod;
    }
    for(int i=mid;i<r;++i) {
        h[i]=(h[i]+temf[i-l])%mod;
    }
    cdq(mid,r);
    return;
}
int main()
{
    scanf("%d",&n);
    init_pow();
    for(int i=1;i<=n;++i) {
        g[i]=1ll*pow(2,1ll*i*(i-1)/2%(mod-1))*invf[i]%mod;
    }
    cdq(0,n+1);
    printf("%d\n",(int)(1ll*f[n]*fac[n-1]%mod+mod)%mod);
    return 0;
}