[BZOJ3456]城市规划 - A-Failure的博客

题目

Description

刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.

刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.

好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目. 由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.

Input

仅一行一个整数n(<=130000)

Output

仅一行一个整数, 为方案数 mod 1004535809.

Sample Input

Sample Output

HINT

对于 100%的数据, n <= 130000

题解

如果要求$n$个点形成的图，那么答案就是$\sum_{i=0}^{C_{n}^{2}}C_{C_{2}^{n}}^i$，即$2^{\frac{n(n-1)}{2}}$

发现所有的图的个数等于某些点形成连通图，其他点任意连的方案数之和

如果设$F(n)=2^{\frac{n(n-1)}{2}}$，$f(n)$表示$n$个点形成连通图的方案数，则有

$F(n)=\sum_{i=1}^{n}f(i)F(n-i)C_{n-1}^{i-1}$

可以这么理解这个式子：$1$号节点肯定要在一个连通块之内，所有考虑枚举$1$号节点所在连通块大小，这样$i$个节点时共有$C_{n-1}^{i-1}$种情况，同时乘上其他随意连的点的方案数

可以把$C_{n-1}^{i-1}$拆开，然后就是$\frac{F(n)}{(n-1)!}=\sum_{i=1}^{n}\frac{f(i)}{(i-1)!}\frac{F(n-i)}{(n-i)!}$

看成$3$个多项式，然后就可以多项式求逆求出$f(x)$了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5.3e5+5,mod=1004535809;
int n,lim=1,L;
int R[MAX],a[MAX],b[MAX],A[MAX],_A[MAX],fac[MAX],Fac[MAX];
int read()
{
    int x(0);
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
    return x;
}
int Pow(int a,LL b)
{
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
      if(b&1) ans=1ll*a*ans%mod;
    return ans;
}
void NTT(int *A,int tt=1)
{
    for(int i=0;i<lim;++i)
      if(i<R[i]) swap(A[i],A[R[i]]);
    for(int i=1,w1;i<lim;i<<=1)
      {
        w1=Pow(3,(mod-1)/(i<<1));
        for(int l=i<<1,w,j=0;j<lim;j+=l)
          {
            w=1;
            for(int k=0,x,y;k<i;++k,w=1ll*w*w1%mod)
              {
                x=A[j+k],y=1ll*w*A[i+j+k]%mod,A[j+k]=x+y,A[i+j+k]=x-y+mod;
                if(A[j+k]>=mod) A[j+k]-=mod;
                if(A[i+j+k]>=mod) A[i+j+k]-=mod;
              }
          }
      }
    if(tt==-1)
    {
        reverse(A+1,A+lim);
        for(int i=0,G=Pow(lim,mod-2);i<lim;++i)
          A[i]=1ll*A[i]*G%mod;
    }
}
void Inv(int *A,int *b,int n)
{
    if(n==1) return void(b[0]=Pow(A[0],mod-2));
    Inv(A,b,n+1>>1),lim=1,L=0;
    while(lim<=2*n-1) lim<<=1,++L;
    for(int i=0;i<=lim;++i)
      R[i]=(R[i>>1]>>1)|((i&1)<<L-1),a[i]=0;
    for(int i=0;i<n;++i)
      a[i]=A[i];
    NTT(a),NTT(b);
    for(int i=0;i<=lim;++i)
      b[i]=(2-1ll*a[i]*b[i]%mod+mod)%mod*b[i]%mod;
    NTT(b,-1);
    for(int i=n;i<=lim;++i)
      b[i]=0;
}
int main()
{
    n=read(),fac[0]=1,Fac[0]=Pow(1,mod-2);
    for(int i=0;i<=n;++i)
      {
        if(i) fac[i]=1ll*fac[i-1]*i%mod,Fac[i]=Pow(fac[i],mod-2);
        A[i]=1ll*Pow(2,1ll*i*(i-1)>>1)*Fac[i]%mod,_A[i]=1ll*A[i]*i%mod;
      }
    Inv(A,b,n);
    while(lim<=2*n-1) lim<<=1,++L;
    for(int i=0;i<=lim;++i)
      R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
    NTT(_A),NTT(b);
    for(int i=0;i<=lim;++i)
      _A[i]=1ll*_A[i]*b[i]%mod;
    return NTT(_A,-1),printf("%d",1ll*_A[n]*fac[n-1]%mod),0;
}

题目