Description
刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了. 刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案. 好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目. 由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.
Input
仅一行一个整数n(<=130000)
Output
仅一行一个整数, 为方案数 mod 1004535809.
Solution
Code
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int p
=1004535809;
int a
[300010],b
[300010],c
[300010],d
[300010];
int rev
[300010],pg
[300010],pinvg
[300010],n
;
int fac
[300010]={1},ifac
[300010];
int qpow(int x
,ll y
){
int s
=1,bas
=x
;
while(y
){
if(y
&1) s
=(s
*1ll*bas
)%p
;
bas
=(bas
*1ll*bas
)%p
;
y
>>=1;
}
return s
;
}
void NTT(int *A
,int limit
,int typ
){
for(int i
=0;i
<limit
;i
++)
if(i
<rev
[i
]) swap(A
[i
],A
[rev
[i
]]);
for(int i
=1;i
<limit
;i
<<=1){
int wn
=typ
>0?pg
[i
<<1]:pinvg
[i
<<1];
for(int j
=0,s
=i
<<1;j
<limit
;j
+=s
)
for(int k
=0,w
=1;k
<i
;k
++,w
=(w
*1ll*wn
)%p
){
int x
=A
[j
+k
],y
=(A
[j
+k
+i
]*1ll*w
)%p
;
A
[j
+k
]=(x
+y
)%p
,A
[j
+k
+i
]=(x
-y
+p
)%p
;
}
}
if(typ
<0){
int inv
=qpow(limit
,p
-2);
for(int i
=0;i
<limit
;i
++)
A
[i
]=(A
[i
]*1ll*inv
)%p
;
}
}
void getinv(int *A
,int *B
,int l
){
if(l
==1){
B
[0]=qpow(A
[0],p
-2);
return;
}
getinv(A
,B
,(l
+1)>>1);
int limit
=1,bit
=0;
while(limit
<2*l
)
limit
<<=1,bit
++;
for(int i
=0;i
<limit
;i
++)
rev
[i
]=(rev
[i
>>1]>>1)|((i
&1)<<(bit
-1));
for(int i
=0;i
<l
;i
++) c
[i
]=A
[i
];
for(int i
=l
;i
<limit
;i
++) c
[i
]=0;
NTT(c
,limit
,1),NTT(B
,limit
,1);
for(register int i
=0;i
<limit
;i
++)
B
[i
]=(2ll-c
[i
]*1ll*B
[i
]%p
+p
)%p
*1ll*B
[i
]%p
; NTT(B
,limit
,-1);
for(int i
=l
;i
<limit
;i
++) B
[i
]=0;
}
int invg
;
void init(int limit
){
invg
=qpow(3,p
-2);
for(int i
=1;i
<=limit
;i
<<=1)
pg
[i
]=qpow(3,(p
-1)/i
);
for(int i
=1;i
<=limit
;i
<<=1)
pinvg
[i
]=qpow(invg
,(p
-1)/i
);
for(int i
=1;i
<=n
;i
++)
fac
[i
]=(fac
[i
-1]*1ll*i
)%p
;
ifac
[n
]=qpow(fac
[n
],p
-2);
for(int i
=n
;i
;i
--)
ifac
[i
-1]=(ifac
[i
]*1ll*i
)%p
;
}
int main(){
a
[0]=1;
scanf("%d",&n
);
int limit
=1,bit
=0;
while(limit
<2*(n
+1))
limit
<<=1,bit
++;
init(limit
);
for(int i
=1;i
<=n
;i
++){
int x
=qpow(2,i
*1ll*(i
-1)/2);
a
[i
]=(x
*1ll*ifac
[i
])%p
;
d
[i
]=(x
*1ll*ifac
[i
-1])%p
;
}
getinv(a
,b
,n
+1);
for(int i
=0;i
<limit
;i
++)
rev
[i
]=(rev
[i
>>1]>>1)|((i
&1)<<(bit
-1));
NTT(b
,limit
,1),NTT(d
,limit
,1);
for(int i
=0;i
<limit
;i
++)
b
[i
]=(b
[i
]*1ll*d
[i
])%p
;
NTT(b
,limit
,-1);
printf("%lld",(b
[n
]*1ll*fac
[n
-1])%p
);
}
