JZOJ 3303. 【集训队互测2013】城市规划
题目
Description
刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.
刚才说过, 阿狸的国家有n 个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通.
为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.
好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n 个点的简单(无重边无自环)无向连通图数目.
由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^21 + 1)即可.
Input
仅一行一个整数n(<=130000)
Output
仅一行一个整数, 为方案数mod 1004535809.
Sample Input
输入1：
3
输入2：
4
输入3：
100000
Sample Output
输出1：
4
输出2：
38
输出3：
829847355
Data Constraint
对于20%的数据, n <= 10
对于40%的数据, n <= 1000
对于60%的数据, n <= 30000
对于80%的数据, n <= 60000
对于100%的数据, n <= 130000
题解
- 这种计数题，按照常规的思路，先考虑一下递推，
- 设 i i i的答案为 f i f_i fi，那么 f i f_i fi可以由 f j ( 1 ≤ j < i ) f_j(1≤j<i) fj(1≤j<i)怎么转移，
- 经过思考后，发现好像不是很可行。
- （也许可以，至少多数人都没有推出来）
- 那我们想想容斥（不要怕），用总方案数减去不可行的方案数（这就是容斥的全部），
- 开始推一波式子：
- f i = 2 C i 2 − ∑ j = 1 i − 1 f j ∗ C i − 1 j − 1 ∗ 2 C i − j 2 f_i=2^{C_i^2}-sum_{j=1}^{i-1}f_j*C_{i-1}^{j-1}*2^{C_{i-j}^2} fi=2Ci2−j=1∑i−1fj∗Ci−1j−1∗2Ci−j2
- 2 C i 2 2^{C_i^2} 2Ci2是 i i i个点之间所有无向边选或不选的总方案数；
- ∑ j = 1 i − 1 sum_{j=1}^{i-1} ∑j=1i−1是枚举任意一个点（比如说 1 1 1号点）所在的连通块的大小；
- f j f_j fj表示该连通块组成的方案数（当点已经确定的情况下）；
- C i − 1 j − 1 C_{i-1}^{j-1} Ci−1j−1是在剩余点中选出与 i i i组成大小为 j j j的连通块的方案数；
- 2 C i − j 2 2_{C_{i-j}^2} 2Ci−j2是该连通块以外的点之间所有边选或不选的方案数；
- 这样可以保证不重不漏！！！
- 设 g i g_i gi表示 2 C i 2 2^{C_i^2} 2Ci2，也就是 i i i个点之间所有无向边选或不选的总方案数，
- f i = 2 C i 2 − ∑ j = 1 i − 1 f j ∗ C i − 1 j − 1 ∗ 2 C i − j 2 f_i=2^{C_i^2}-sum_{j=1}^{i-1}f_j*C_{i-1}^{j-1}*2^{C_{i-j}^2} fi=2Ci2−j=1∑i−1fj∗Ci−1j−1∗2Ci−j2
- = g i − ∑ j = 1 i − 1 f j ∗ C i − 1 j − 1 ∗ g i − j =g_i-sum_{j=1}^{i-1}f_j*C_{i-1}^{j-1}*g_{i-j} =gi−j=1∑i−1fj∗Ci−1j−1∗gi−j
- = g i − ∑ j = 1 i − 1 f j ∗ ( i − 1 ) ! ( j − 1 ) ! ( i − j ) ! ∗ g i − j =g_i-sum_{j=1}^{i-1}f_j*frac{(i-1)!}{(j-1)!(i-j)!}*g_{i-j} =gi−j=1∑i−1fj∗(j−1)!(i−j)!(i−1)!∗gi−j
- = g i − ( i − 1 ) ! ∑ j = 1 i − 1 f j ( j − 1 ) ! ∗ g i − j ( i − j ) ! =g_i-(i-1)!sum_{j=1}^{i-1}frac{f_j}{(j-1)!}*frac{g_{i-j}}{(i-j)!} =gi−(i−1)!j=1∑i−1(j−1)!fj∗(i−j)!gi−j
- 右边显然是个卷积的形式，用 N T T NTT NTT来做，
- 但是要做 n n n次，那么用分治 N T T NTT NTT.
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define md 1004535809
#define LL long long
#define N 300010
LL f[N],g[N],q[N],ny[N],ws[N],wt[N],nn[N];
LL a[N],b[N],rev[N];
LL ksm(LL x,LL y)
{
if(!y) return 1;
LL l=ksm(x,y/2);
if(y%2) return l*l%md*x%md;
return l*l%md;
}
void NTT(LL *a,int ln,int p)
{
for(int i=0;i<ln;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=1;i<ln;i*=2)
{
LL w=ws[i*2];
if(p==-1) w=wt[i*2];
for(int j=0;j<ln;j+=2*i)
{
LL w0=1;
for(int k=0;k<i;k++)
{
LL A=a[k+j],B=w0*a[k+j+i];
a[k+j]=(A+B%md)%md;
a[k+j+i]=(A-B%md+md)%md;
w0=w0*w%md;
}
}
}
if(p==-1)
{
for(LL i=0;i<ln;i++) a[i]=a[i]*nn[ln]%md;
}
}
void cdq(LL l,LL r)
{
if(l==r)
{
f[l]=(g[l]-f[l]*q[l-1]%md+md)%md;
}
else
{
int mid=(l+r)/2,t=0,s=1,i;
cdq(l,mid);
for(;s<(r-l+1);s*=2) t++;
s*=2;
rev[0]=0;
for(i=1;i<s;i++) rev[i]=rev[i/2]/2|((i&1)<<t);
for(i=0;i<=mid-l;i++) a[i]=f[i+l]*ny[i+l-1]%md;
for(i=mid-l+1;i<s;i++) a[i]=0;
for(i=1;i<=r-l;i++) b[i]=g[i]*ny[i]%md;
b[0]=0;
for(i=r-l+1;i<s;i++) b[i]=0;
NTT(a,s,1),NTT(b,s,1);
for(i=0;i<s;i++) a[i]=a[i]*b[i]%md;
NTT(a,s,-1);
for(i=1;i<=mid-l+1;i++) f[i+mid]=(f[i+mid]+a[i+mid-l])%md;
cdq(mid+1,r);
}
}
int main()
{
LL n,i,j;
scanf("%lld",&n);
LL ln=1;
for(;ln<n;ln*=2);
q[0]=1,ny[0]=1;
for(i=1;i<=ln*2;i++) q[i]=q[i-1]*i%md;
ny[ln*2]=ksm(q[ln*2],md-2);
for(i=ln*2-1;i;i--) ny[i]=ny[i+1]*(i+1)%md;
for(i=1;i<=ln*2;i++) g[i]=ksm(2,1ll*i*(i-1)/2);
for(i=1;i<=ln*2;i++) nn[i]=ksm(i,md-2);
for(i=1;i<=ln*2;i*=2) ws[i]=ksm(3,(md-1)/i),wt[i]=ksm(ws[i],md-2);
cdq(1,ln);
printf("%lld",f[n]);
return 0;
}