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

题目链接

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

Solution

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

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

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

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

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

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

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

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

#define P 1004535809LL

#define G 3LL

#define MAXN 800010

int 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<len-1; i++) {

		if (i<j) swap(x[i],x[j]);

		k=len>>1;

		while (j>=k) j-=k,k>>=1;

		if (j<k) j+=k;

	}

}

inline void DFT(int *x,int opt)

{

	Rader(x);

	for (register int h=2,id=0; h<=len; h<<=1) {

		LL Wn=wn[++id];

		for (register int i=0; i<len; i+=h) {

			LL W=1;

			for (register int j=i; j<i+h/2; j++) {

				LL u=(LL)x[j]%P,t=(LL)W*x[j+h/2]%P;

				x[j]=(u+t)%P; x[j+h/2]=(u-t+P)%P;

				W=W*Wn%P;

			}

		}

	}

	if (opt==-1) {

		for (register int i=1; i<len/2; i++) swap(x[i],x[len-i]);

		for (register int i=0; i<len; i++) x[i]=(LL)x[i]*Inv(len)%P;

	}

}

inline void NTT()

{

	DFT(A,1); DFT(B,1);

	for (register int i=0; i<len; i++) ans[i]=(LL)A[i]*B[i]%P;

	DFT(ans,-1);

}

int C2[MAXN],fac[MAXN],ifac[MAXN];

inline void CDQ(int l,int r)

{

	if (l==r) {

		dp[l]=(C2[l]-(LL)dp[l]*fac[l-1]%P+P)%P; return;

	}

	int mid=(l+r)>>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<len; i++) A[i]=B[i]=0;

	NTT();

	for (register int i=mid+1; i<=r; i++) (dp[i]+=ans[i-l])%=P;

	CDQ(mid+1,r);

}

int main()

{

//	freopen("count.in","r",stdin);

//	freopen("count.out","w",stdout);

	scanf("%d",&N);

	for (register int i=0; i<=30; i++) wn[i]=Pow(G,(P-1)/(1<<i));

	fac[0]=ifac[0]=1;

	for (register int i=1; i<=N; i++) fac[i]=((LL)fac[i-1]*i)%P,ifac[i]=Inv(fac[i]);

	for (register int i=1; i<=N; i++) C2[i]=Pow(2LL,(LL)((LL)i*(i-1))/2);

	CDQ(1,N);

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

	return 0;

}

巴特西

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

题目链接

Solution

Code

最新文章

热门文章