bzoj 3456 城市规划 —— 分治FFT / 多项式求逆 / 指数型生成函数(多项式求ln)

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3456

首先考虑DP做法，正难则反，考虑所有情况减去不连通的情况；

而不连通的情况就是那个经典做法：选定一个划分点，枚举包含它的连通块，连通块以外的部分随便连(但不和连通块连通)，合起来就是不连通的方案数；

设 \( f[i] \) 表示一共 \( i \) 个点时的连通方案数，\( g[i] \) 表示 \( i \) 个点随便连的方案数，即 \( g[i] = 2^{C_{i}^{2}} \)，则：

\( f[i] = 2^{C_{i}^{2}} - \sum\limits_{j=1}^{i-1} C_{i-1}^{j-1} * f_{j} * g_{i-j} \)

只要令 \( g[0] = 0 \)，\( j \) 就可以枚举到 \( i \)；

把 \( C_{i-1}^{j-1} \) 拆开，对应分配到各处，得到：

\( f[i] = 2^{C_{i}^{2}} - (i-1)!*\sum\limits_{j=1}^{i}\frac{f_{j}}{(j-1)!} * \frac{g_{i-j}}{(i-j)!} \)

所以把 \( g[i] \) 的定义改成 \( g[i] = \frac{2^{C_{i}^{2}}}{i!} \)

于是 \( f[i] = 2^{C_{i}^{2}} - (i-1)!*\sum\limits_{j=1}^{i}\frac{f_{j}}{(j-1)!} * g_{i-j} \)

然后就可以分治FFT了；

很容易写错的地方是那个 \( 2^{C_{i}^{2}} \)，因为是指数，所以应该对 \( mod-1 \) 取模，而不是 \( mod \) ！！

而且除以 \( 2 \) 也不能预处理 \( inv2 \) 了，因为 \( mod-1 \) 不是质数！！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=(<<),mod=;

int n,f[xn],g[xn],jc[xn],jcn[xn],a[xn],b[xn],rev[xn],inv2,in[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,int b,int p=mod)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%p)if(b&)ret=(ret*a)%p;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

int C(int x){return ((ll)x*(x-)/)%(mod-);}//mod-1!!!  //not inv2 -- !pri

void init()

{

  jc[]=;

  for(int i=;i<=n;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[n]=pw(jc[n],mod-);

  for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

  g[]=;

  for(int i=;i<=n;i++)g[i]=(ll)pw(,C(i))*jcn[i]%mod;

}

void ntt(int *a,int tp,int lim)

{

  for(int i=;i<lim;i++)

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      int len=(mid<<),wn=pw(,tp==?(mod-)/len:(mod-)-(mod-)/len);

      for(int j=;j<lim;j+=len)

    for(int k=,w=;k<mid;k++,w=(ll)w*wn%mod)

      {

        int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;

        a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);

      }

    }

  if(tp==)return; int inv=pw(lim,mod-);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*inv%mod;

}

void work(int l,int r)

{

  if(l==r){f[l]=upt((ll)pw(,C(l))-(ll)jc[l-]*f[l]%mod); return;}

  int len=r-l+,mid=((l+r)>>);

  work(l,mid);

  int lim=,L=;

  while(lim<=len)lim<<=,L++;//

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(L-)));

  for(int i=;i<lim;i++)a[i]=b[i]=;

  for(int i=l;i<=mid;i++)a[i-l]=(ll)f[i]*jcn[i-]%mod;//jcn!!

  for(int i=;i<=r-l;i++)b[i]=g[i];//

  ntt(a,,lim); ntt(b,,lim);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*b[i]%mod;

  ntt(a,-,lim);

  for(int i=mid+;i<=r;i++)f[i]=upt(f[i]+a[i-l]);

  work(mid+,r);

}

int main()

{

  n=rd(); init();

  work(,n);

  printf("%d\n",f[n]);

  return ;

}

分治FFT

也可以用多项式求逆做：

设 \( g[i] = 2^{C_{i}^{2}} \)，这里 \( g[0] = 1 \)，\( f[i] \) 定义同上；

得到 \( g[n] = \sum\limits_{i=1}^{n} C_{n-1}^{i-1} * f[i] * g[n-i] \)

拆 \( C_{n-1}^{i-1} \)，得到

\( \frac{g[n]}{(n-1)!} = \sum\limits_{i=1}^{n} \frac{f[i]}{(i-1)!} * \frac{g[n-i]}{(n-i)!} \)

设 \( A[i] = \frac{g[i]}{(i-1)!} \) ， \( B[i] = \frac{f[i]}{(i-1)!} \) ， \( C[i] = \frac{g[i]}{i!} \)

注意这里 \( A[0] = 0 \) ， \( B[0] = 0 \) ， \( C[0] = 1 \)

所以 \( A(x) = B(x) * C(x) \)

即 \( B(x) = A(x) * C^{-1}(x) ( mod x^{n+1} ) \)

多项式求逆即可；

别忘了外层的乘法还要处理一下 \( rev \) 数组。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=(<<),mod=;

int n,a[xn],b[xn],c[xn],t[xn],rev[xn],jc[xn],jcn[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,int b)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

int C(int x){return ((ll)x*(x-)/)%(mod-);}

void init()

{

  jc[]=;

  for(int i=;i<=n;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[n]=pw(jc[n],mod-);

  for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

void ntt(int *a,int tp,int lim)

{

  for(int i=;i<lim;i++)

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      int len=(mid<<),wn=pw(,tp==?(mod-)/len:(mod-)-(mod-)/len);

      for(int j=;j<lim;j+=len)

    for(int k=,w=;k<mid;k++,w=(ll)w*wn%mod)

      {

        int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;

        a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);

      }

    }

  if(tp==)return; int inv=pw(lim,mod-);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*inv%mod;

}

void inv(int *a,int *b,int n)

{

  if(n==){b[]=pw(a[],mod-); return;}

  inv(a,b,(n+)>>);

  int lim=,l=;

  while(lim<n+n)lim<<=,l++;

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(l-)));

  for(int i=;i<n;i++)t[i]=a[i];

  for(int i=n;i<lim;i++)t[i]=;

  ntt(t,,lim); ntt(b,,lim);

  for(int i=;i<lim;i++)b[i]=upt((-(ll)t[i]*b[i])%mod*b[i]%mod);

  ntt(b,-,lim);

  for(int i=n;i<lim;i++)b[i]=;

}

int main()

{

  n=rd(); init();

  int lim=,l=;

  while(lim<=n)lim<<=,l++;

  for(int i=;i<lim;i++)a[i]=(ll)pw(,C(i))*jcn[i-]%mod;

  for(int i=;i<lim;i++)c[i]=(ll)pw(,C(i))*jcn[i]%mod;

  c[]=;

  inv(c,b,n+);

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(l-)));//!!!

  ntt(a,,lim); ntt(b,,lim);

  for(int i=;i<lim;i++)b[i]=(ll)a[i]*b[i]%mod;

  ntt(b,-,lim);

  printf("%lld\n",(ll)b[n]*jc[n-]%mod);

  return ;

}

多项式求逆

也可以用指数型生成函数，具体做法可以看这篇博客：https://blog.csdn.net/wzq_qwq/article/details/48435621

关于为什么 \( G(x) = e^{F(x)} \)

因为从组合意义上来看，任意无向图实际上可以分为：由0个连通图组成(没有点)，由1个连通图组成，由2个连通图组成(这2个之间不连通)，由3个连通图组成...

所以 \( G(x) = 1 + \frac{F(x)}{1!} + \frac{F(x)^{2}}{2!} + \frac{F(x)^{3}}{3!} + ... \)

即 \( G(x) = e^{F(x)} \)

而 \( G(x) \) 很好构造，求 \( F(x) = lnG(x) \)

求 \( ln \) 的方法可以看这两篇博客：

https://blog.csdn.net/litble/article/details/81749788

https://blog.csdn.net/ezoixx118/article/details/81235586

直接用上公式...这题原来是多项式求 \( ln \) 的裸题；

别忘了最后乘上 \( n! \)

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=(<<),mod=;

int n,g[xn],dg[xn],ig[xn],t[xn],rev[xn],jc[xn],jcn[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,ll b)

{

  ll ret=; b=b%(mod-);

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void init()

{

  jc[]=;

  for(int i=;i<=n;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[n]=pw(jc[n],mod-);

  for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

void ntt(int *a,int tp,int lim)

{

  for(int i=;i<lim;i++)

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      int len=(mid<<),wn=pw(,tp==?(mod-)/len:(mod-)-(mod-)/len);

      for(int j=;j<lim;j+=len)

    for(int k=,w=;k<mid;k++,w=(ll)w*wn%mod)

      {

        int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;

        a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);

      }

    }

  if(tp==)return; int inv=pw(lim,mod-);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*inv%mod;

}

void inv(int *a,int *b,int n)

{

  if(n==){b[]=pw(a[],mod-); return;}

  inv(a,b,(n+)>>);

  int lim=,l=;

  while(lim<n+n)lim<<=,l++;

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(l-)));

  for(int i=;i<n;i++)t[i]=a[i];

  for(int i=n;i<lim;i++)t[i]=;

  ntt(t,,lim); ntt(b,,lim);

  for(int i=;i<lim;i++)b[i]=upt((-(ll)t[i]*b[i])%mod*b[i]%mod);

  ntt(b,-,lim);

  for(int i=n;i<lim;i++)b[i]=;

}

int main()

{

  n=rd(); init();

  for(int i=;i<=n;i++)

    {

      if(i<)g[i]=;

      g[i]=(ll)pw(,(ll)i*(i-)/)*jcn[i]%mod;

    }

  for(int i=;i<=n;i++)dg[i-]=(ll)i*g[i]%mod;

  dg[n]=;//

  inv(g,ig,n+);

  int lim=,l=;

  while(lim<n+n)lim<<=,l++;

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(l-)));

  ntt(ig,,lim); ntt(dg,,lim);

  for(int i=;i<lim;i++)dg[i]=(ll)ig[i]*dg[i]%mod;

  ntt(dg,-,lim);

  printf("%lld\n",(ll)dg[n-]*pw(n,mod-)%mod*jc[n]%mod);

  return ;

}

多项式求ln

巴特西

bzoj 3456 城市规划 —— 分治FFT / 多项式求逆 / 指数型生成函数(多项式求ln)

最新文章

热门文章