题目链接

题解

nn个点构成的连通图数量为

g(n)=2(n2)g(n)=2(n2)

枚举

11号点所在连通块的大小，得到

gn=∑i=1n(n−1i−1)fign−ign=∑i=1n(n−1i−1)fign−i

因此

2(n2)=∑i=1n(n−1)!(i−1)!(n−i)!fign−i2(n2)=∑i=1n(n−1)!(i−1)!(n−i)!fign−i

整理得到

2(n2)(n−1)!=∑i=1nfi(i−1)!2(n−i2)(n−i)!2(n2)(n−1)!=∑i=1nfi(i−1)!2(n−i2)(n−i)!

令

F=fi(i−1)!xi,G=2(i2)i!xi,T=2(i2)(i−1)!xiF=fi(i−1)!xi,G=2(i2)i!xi,T=2(i2)(i−1)!xi

则有

T=FG(modxn+1)T=FG(modxn+1)

即

F=TG−1(modxn+1)F=TG−1(modxn+1)

先求出

GG和

TT，求

GG的逆元，卷积一遍就可以得到

FF，得到

FF之后很容易得到

fifi。

代码

#include 
    
     #include 
     
      #include 
      
       int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=300000;const int mod=1004535809;const int G=3;int quickpow(int a,int b,int m){  int res=1;  while(b)    {      if(b&1)        {          res=1ll*res*a%m;        }      a=1ll*a*a%m;      b>>=1;    }  return res;}int plus(int a,int b,int m){  int res=a+b;  if(res>=m)    {      res-=m;    }  return res;}int minus(int a,int b,int m){  int res=a-b;  if(res<0)    {      res+=m;    }  return res;}int rev[maxn+10],tmp[maxn+10];int getrev(int n){  int m=1,len=0;  while(m<=n)    {      m<<=1;      ++len;    }  for(int i=0; i
       
        >1]>>1)+((i&1)<<(len-1));    }  return m;}int fft(int *s,int len){  for(int i=0; i
        
         >1); ++k)            {              int x=s[j+k],y=1ll*g*s[j+k+(i>>1)]%mod;              s[j+k]=plus(x,y,mod);              s[j+k+(i>>1)]=minus(x,y,mod);              g=1ll*g*gn%mod;            }        }    }  return 0;}int getinv(int *s,int *v,int deg){  if(deg==1)    {      v[0]=quickpow(s[0],mod-2,mod);      return 0;    }  getinv(s,v,(deg+1)>>1);  int p=getrev(deg<<1);  for(int i=0; i