【BZOJ-3456】城市规划 CDQ分治 + NTT

题目链接

　　http://www.lydsy.com/JudgeOnline/problem.php?id=3456

Solution

这个问题可以考虑dp，利用补集思想

N个点的简单图总数量为$2^{inom{N}{2}}$，要求的是简单联通图，所以可以用总量减不连通的。

不连通的可以通过枚举与某个固定点的联通的点的数量得到$tot=sum _{i=1} ^{N} inom{N-1}{i-1}*dp[i]*2^{inom{N-i}{2}}$

其中$dp[i]$表示的就是$i$个点的联通图数量。

然后将公式稍稍变型整理成$frac{dp[N]}{(N-1)!}=frac{2^{inom{N}{2}}}{(N-1)!}-sum_{i=1}^{N-1}frac{dp[i]}{(i-1)!}*frac{2^{inom{N-i}{2}}}{(N-i)!}$

这个式子可以利用 CDQ分治+NTT 在$O(Nlog^{2}N)$的时间得到。

 

至于这道题吗，显然是可以多项式求逆来做的，复杂度$O(NlnN)$，上述做法自己写的被卡常了，不过本机效果还不错，留下代码以后看看。

Code

#include
#include
#include
#include
#include
using namespace std;
#define LL long long#define P 1004535809LL
#define G 3LL#define MAXN 800010int N,len;inline LL Pow(LL x,LL y) {LL re=1; for (LL i=y; i; i>>=1,x=x*x%P) if (i&1) re=re*x%P; return re;}inline LL Inv(LL x) {return Pow(x,P-2);}int A[MAXN],B[MAXN],ans[MAXN],wn[31],dp[MAXN];inline void Rader(int *x)
{for (register int i=1,j=len>>1,k; i>1;while (j>=k) j-=k,k>>=1;if (j>1;CDQ(l,mid);for (register int i=l; i<=mid; i++) A[i-l]=(LL)dp[i]*ifac[i-1]%P;for (register int i=0; i<=r-l; i++) B[i]=(LL)C2[i]*ifac[i]%P;for (register int i=mid-l+1; i<=r-l; i++) A[i]=0;len=1; while (len<((r-l+1)<<1)) len<<=1;for (register int i=r-l+1; i