3456 - 城市规划

题解bymod998244353

广告：多项式全家桶

方法一：

设 f_i 表示 i 个点的有标号无向连通图数目，g_i 表示 i 个点的有标号无向连通图数目，则g_i=2^{C^2_n}，f_n为答案。

n 个点有标号无向连通图数目为 i 个点的有标号无向连通图数目乘上 n-i个点的有标号无向连通图数目得到：

g_i=\sum\limits_{i=1}^nC_{n-1}^{i-1}f_ig_{n-i}

\dfrac{g_i}{(n-1)!}=\sum\limits_{i=1}^n\dfrac{f_i}{(i-1)!}\dfrac{g_{n-i}}{(n-i)!}

\dfrac{g_i}{(n-1)!}x^n=\sum\limits_{i=1}^n(\dfrac{f_i}{(i-1)!}x^i)(\dfrac{g_{n-i}}{(n-i)!}x^{n-i})

也就是\sum\limits_{i=1}^{\infty}\dfrac{g_i}{(i-1)!}x^i=(\sum\limits_{i=1}^{\infty}\dfrac{f_i}{(i-1)!}x^i)(\sum\limits_{i=0}^{\infty}\dfrac{g_{n-i}}{(n-i)!}x^{n-i})

设F(x)=\sum\limits_{i=1}^{\infty}\dfrac{g_i}{(i-1)!}x^i,G(x)=\sum\limits_{i=1}^{\infty}\dfrac{f_i}{(i-1)!}x^i,H(x)=\sum\limits_{i=0}^{\infty}\dfrac{g_i}{i!}x^i

则G(x)=F(x)\times H^{-1}(x)，多项式求逆即可：

#include<bits/stdc++.h>
using namespace std;
const int MAXM=18,MAXN=1<<MAXM,mod=1004535809,pmod=mod-1,G=3,Gi=(mod+1)/G,inv2=mod+1>>1;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
  int x=0,c=getchar();
  for(; c<=47||c>=58; c=getchar());
  for(; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
  return x;
}
int TTTTTTT,RRRRRRR[MAXN],omega[2][MAXN],fac[MAXN],ifac[MAXN],inv[MAXN];
int fastpow(int a,int k)
{
  int base=1;
  for(; k; a=((0ll+a)*a)%mod,k>>=1)
    if(k&1)
      base=((0ll+base)*a)%mod;
  return base%mod;
}
void tpre(int limit)
{
  if(limit==TTTTTTT)return ;
  else TTTTTTT=limit;
  for(int i=0,p=limit>>1; i<limit; ++i)
    if(i&1)RRRRRRR[i]=(RRRRRRR[i>>1]>>1)|p;
    else RRRRRRR[i]=RRRRRRR[i>>1]>>1;
}
void NTT(int*a,bool op,int limit)
{
  if(limit==1)return;
  static ull A[MAXN];
  tpre(limit);
  for(int i=0; i<limit; ++i)A[i]=a[RRRRRRR[i]];
  for(int mid=1,l=2,L=1; l<=limit; mid=l,l<<=1,++L)
  {
    for(int j=0,TT=MAXM-L; j<limit; j+=l)
    {
      for(int k=0; k<mid; ++k)
      {
        int u=j|k,v=u|mid,x=(omega[op][k<<TT]*A[v]%mod);
        ull y=A[u];
        A[v]=y+mod-x;
        A[u]=y+x;
      }
    }
    if(L==17)
      for(int i=0; i<limit; ++i)A[i]%=mod;
  }
  if(!op)
  {
    ull inv=fastpow(limit,mod-2);
    for(int i=0; i<limit; ++i)
      a[i]=A[i]*inv%mod;
  }
  else
    for(int i=0; i<limit; ++i)
      a[i]=A[i]%mod;
}

void px(int*f,int*g,int n)
{
  for(int i=0; i<n; ++i)f[i]=(0ll+f[i])*g[i]%mod;
}
void clr(int*f,int n)
{
  memset(f,0,n<<2);
}
void cpy(int*f,int*g,int n)
{
  memcpy(f,g,n<<2);
}
void print(int*f,int n)
{
  for(int i=0; i<n; ++i)printf("%d ",f[i]);
  putchar(10);
}

int sav[MAXN],WW[MAXN],RR[MAXN];
void times(int *f,int *g,int len,int lim)
{
  int n=1;
  for(n; n<len+len; n<<=1);
  cpy(sav,g,n);
  for(int i=len; i<n; ++i)sav[i]=0;
  NTT(f,1,n);
  NTT(sav,1,n);
  px(f,sav,n);
  NTT(f,0,n);
  for(int i=lim; i<n; ++i)f[i]=0;
  clr(sav,n);
}

void savtimes(int *f,int *g,int len1,int len2,int lim)
{
  static int s1[MAXN],s2[MAXN];
  cpy(s1,f,len1);
  cpy(s2,g,len2);
  times(s1,s2,max(len1,len2),lim);
  cpy(f,s1,lim);
  clr(s1,lim);
  clr(s2,len2);
}

void poly_inv(int*f,int m)
{
  int n=1;
  for(; n<m; n<<=1);
  WW[0]=fastpow(f[0],mod-2);
  for(int len=2; len<=n; len<<=1)
  {
    for(int i=0,LEN=len>>1; i<LEN; ++i)
    {
      RR[i]=WW[i]<<1;
      if(RR[i]>=mod)RR[i]-=mod;
    }
    cpy(sav,f,len);
    NTT(WW,1,len<<1);
    px(WW,WW,len<<1);
    NTT(sav,1,len<<1);
    px(WW,sav,len<<1);
    NTT(WW,0,len<<1);
    clr(WW+len,len);
    for(int i=0; i<len; ++i)
    {
      WW[i]=RR[i]-WW[i];
      if(WW[i]<0)
        WW[i]+=mod;
    }
  }
  cpy(f,WW,m),clr(sav,n<<1),clr(WW,n<<1),clr(RR,n<<1);
}

int f[MAXN],g[MAXN],n;
int main()
{
  ull wn=omega[1][1]=fastpow(G,mod>>MAXM),invwn=omega[0][1]=fastpow(Gi,mod>>MAXM);
  omega[0][0]=omega[1][0]=inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
  for(int i=2; i<MAXN; ++i)
  {
    omega[1][i]=omega[1][i-1]*wn%mod,omega[0][i]=omega[0][i-1]*invwn%mod;
    inv[i]=inv[mod%i]*(mod+0ll-mod/i)%mod;
    fac[i]=fac[i-1]*1ll*i%mod;
    ifac[i]=ifac[i-1]*1ll*inv[i]%mod;
  }
  n=read()+1,g[0]=1;
  for(int i=1; i<n; ++i)
  {
    ll power=fastpow(2,i*1ll*(i-1)/2%pmod);
    g[i]=power*ifac[i]%mod,f[i]=power*ifac[i-1]%mod;
  }
  poly_inv(g,n),times(f,g,n,n);
  printf("%d\n",fac[n-2]*1ll*f[n-1]%mod);
  return 0;
}

方法二：

设 f_i 表示 i 个点的有标号无向连通图数目除以i!，g_i 表示 i 个点的有标号无向连通图数目除以i!，F(x)=\sum\limits_{i=0}^{\infty}f_ix^i，G(x)=\sum\limits_{i=0}^{\infty}g_ix^i，则g_i=\dfrac{2^{C^2_n}}{i!}，f_n\times n!为答案。

再来探究一下 F 和 G 的关系，可以发现一个无向图就是由若干个无向连通图组成的，因此我们可以枚举组成这个无向图的连通块个数计算贡献。假设我们当前枚举的是 k 个，它的贡献就为：\dfrac{F^k}{k!}

除以k!的原因是为了每个F^k消除标号的影响：F^k 所乘的 k 个元素是有先后顺序之分的，因此需要除以全排列的数目 k!

那么就有：G(x)=\sum\limits_{k=0}^{\infty}F_k(x)=\exp(F(x))

F(x)=\ln(G(x))，多项式\ln即可：

#include<bits/stdc++.h>
using namespace std;
const int MAXM=18,MAXN=1<<MAXM,mod=1004535809,pmod=mod-1,G=3,Gi=(mod+1)/G,inv2=mod+1>>1;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
  int x=0,c=getchar();
  for(; c<=47||c>=58; c=getchar());
  for(; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
  return x;
}
int TTTTTTT,RRRRRRR[MAXN],omega[2][MAXN],fac[MAXN],ifac[MAXN],inv[MAXN];
int fastpow(int a,int k)
{
  int base=1;
  for(; k; a=((0ll+a)*a)%mod,k>>=1)
    if(k&1)
      base=((0ll+base)*a)%mod;
  return base%mod;
}
void tpre(int limit)
{
  if(limit==TTTTTTT)return ;
  else TTTTTTT=limit;
  for(int i=0,p=limit>>1; i<limit; ++i)
    if(i&1)RRRRRRR[i]=(RRRRRRR[i>>1]>>1)|p;
    else RRRRRRR[i]=RRRRRRR[i>>1]>>1;
}
void NTT(int*a,bool op,int limit)
{
  if(limit==1)return;
  static ull A[MAXN];
  tpre(limit);
  for(int i=0; i<limit; ++i)A[i]=a[RRRRRRR[i]];
  for(int mid=1,l=2,L=1; l<=limit; mid=l,l<<=1,++L)
  {
    for(int j=0,TT=MAXM-L; j<limit; j+=l)
    {
      for(int k=0; k<mid; ++k)
      {
        int u=j|k,v=u|mid,x=(omega[op][k<<TT]*A[v]%mod);
        ull y=A[u];
        A[v]=y+mod-x;
        A[u]=y+x;
      }
    }
    if(L==17)
      for(int i=0; i<limit; ++i)A[i]%=mod;
  }
  if(!op)
  {
    ull inv=fastpow(limit,mod-2);
    for(int i=0; i<limit; ++i)
      a[i]=A[i]*inv%mod;
  }
  else
    for(int i=0; i<limit; ++i)
      a[i]=A[i]%mod;
}

void px(int*f,int*g,int n)
{
  for(int i=0; i<n; ++i)f[i]=(0ll+f[i])*g[i]%mod;
}
void clr(int*f,int n)
{
  memset(f,0,n<<2);
}
void cpy(int*f,int*g,int n)
{
  memcpy(f,g,n<<2);
}
void print(int*f,int n)
{
  for(int i=0; i<n; ++i)printf("%d ",f[i]);
  putchar(10);
}

int sav[MAXN],WW[MAXN],RR[MAXN];
void times(int *f,int *g,int len,int lim)
{
  int n=1;
  for(n; n<len+len; n<<=1);
  cpy(sav,g,n);
  for(int i=len; i<n; ++i)sav[i]=0;
  NTT(f,1,n);
  NTT(sav,1,n);
  px(f,sav,n);
  NTT(f,0,n);
  for(int i=lim; i<n; ++i)f[i]=0;
  clr(sav,n);
}

void savtimes(int *f,int *g,int len1,int len2,int lim)
{
  static int s1[MAXN],s2[MAXN];
  cpy(s1,f,len1);
  cpy(s2,g,len2);
  times(s1,s2,max(len1,len2),lim);
  cpy(f,s1,lim);
  clr(s1,lim);
  clr(s2,len2);
}

void poly_inv(int*f,int m)
{
  int n=1;
  for(; n<m; n<<=1);
  WW[0]=fastpow(f[0],mod-2);
  for(int len=2; len<=n; len<<=1)
  {
    for(int i=0,LEN=len>>1; i<LEN; ++i)
    {
      RR[i]=WW[i]<<1;
      if(RR[i]>=mod)RR[i]-=mod;
    }
    cpy(sav,f,len);
    NTT(WW,1,len<<1);
    px(WW,WW,len<<1);
    NTT(sav,1,len<<1);
    px(WW,sav,len<<1);
    NTT(WW,0,len<<1);
    clr(WW+len,len);
    for(int i=0; i<len; ++i)
    {
      WW[i]=RR[i]-WW[i];
      if(WW[i]<0)
        WW[i]+=mod;
    }
  }
  cpy(f,WW,m),clr(sav,n<<1),clr(WW,n<<1),clr(RR,n<<1);
}

void poly_dao(int*f,int n)
{
  if(!n)return;
  for(int i=1; i!=n; ++i)
    f[i-1]=(0ll+f[i])*i%mod;
  f[n-1]=0;
}
void poly_jifen(int*f,int n)
{
  for(int i=n; i; --i)f[i]=(f[i-1]+0ll)*inv[i]%mod;
  f[0]=0;
}
void poly_ln(int*f,int n)
{
  static int FF[MAXN];
  cpy(FF,f,n);
  poly_inv(FF,n);
  poly_dao(f,n);
  times(f,FF,n,n);
  clr(FF,n<<1);
  poly_jifen(f,n-1);
}

int f[MAXN],n;
int main()
{
  ull wn=omega[1][1]=fastpow(G,mod>>MAXM),invwn=omega[0][1]=fastpow(Gi,mod>>MAXM);
  omega[0][0]=omega[1][0]=inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
  for(int i=2; i<MAXN; ++i)
  {
    omega[1][i]=omega[1][i-1]*wn%mod,omega[0][i]=omega[0][i-1]*invwn%mod;
    inv[i]=inv[mod%i]*(mod+0ll-mod/i)%mod;
    fac[i]=fac[i-1]*1ll*i%mod;
    ifac[i]=ifac[i-1]*1ll*inv[i]%mod;
  }
  n=read()+1;
  for(int i=0; i<n; ++i)
    f[i]=fastpow(2,i*1ll*(i-1)/2%pmod)*1ll*ifac[i]%mod;
  poly_ln(f,n);
  printf("%d\n",fac[n-1]*1ll*f[n-1]%mod);
  return 0;
}