【BZOJ3456】城市规划

  模板题。CDQ分治+FFT可以低飞过去。

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const LL PN=2097152,p=1004535809,g=3,gn=702606812;

int Pow(LL x,LL pow)
{
	LL res=1;
	for (;pow;pow>>=1,(x*=x)%=p) if (pow&1) (res*=x)%=p;
	return res;
}

int rev[PN];

void FFT(int *a,int N,int f)
{
	for (int i=0;i<N;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (int i=1;i<N;i<<=1)
	{
		LL wn=Pow(gn,(f==1)?((PN/i)>>1):PN-((PN/i)>>1));
		for (int j=0;j<N;j+=(i<<1))
		{
			LL w=1;
			for (int k=0;k<i;k++,(w*=wn)%=p)
			{
				LL x=a[j+k],y=(LL)a[j+k+i]*w%p;
				a[j+k]=(x+y)%p,a[j+k+i]=(x-y+p)%p;
			}
		}
	}
	LL invN=Pow(N,p-2);
	if (f==-1) for (int i=0;i<N;i++) a[i]=(LL)a[i]*invN%p;
}

void Polynomial_Multyply(int *a,int *b,int n,int m,int *c)
{
	int N=1;
	while (N<n+m-1) N<<=1;
	for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
	for (int i=n;i<N;i++) a[i]=0;
	for (int i=m;i<N;i++) b[i]=0;
	for (int i=0;i<N;i++) c[i]=0;
	FFT(a,N,1);FFT(b,N,1);
	for (int i=0;i<N;i++) c[i]=(LL)a[i]*b[i]%p;
	FFT(c,N,-1);
}

int a[PN],b[PN],invb[PN];
int tempA[PN],tempB[PN],tempC[PN];

void Solve(int *f,int l,int n)
{
	if (n==1) return;
	int mid=(n+1)>>1;
	Solve(f,l,mid);
	for (int i=0;i<mid;i++) tempA[i]=(LL)f[i]*invb[i+l]%p;
	for (int i=0;i<n-1;i++) tempB[i]=(LL)a[i+1]*invb[i+2]%p;
	Polynomial_Multyply(tempA,tempB,mid,n-1,tempC);
	for (int i=mid;i<n;i++) f[i]=(f[i]-(LL)b[i+l]*tempC[i-1]%p+p)%p;
	Solve(f+mid,l+mid,n-mid);
}

int f[PN];
int n;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) a[i]=Pow(2,(LL)i*(i-1)/2);
	b[1]=1;
	for (int i=2;i<=n;i++) b[i]=(LL)b[i-1]*(i-1)%p;
	for (int i=1;i<=n;i++) invb[i]=Pow(b[i],p-2);
	for (int i=1;i<=n;i++) f[i]=a[i];
	Solve(f+1,1,n);
	printf("%d\n",f[n]);
	return 0;
}

多项式逆元

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const LL PN=2097152,p=1004535809,g=3,gn=702606812;

int Pow(LL x,LL pow)
{
	LL res=1;
	for (;pow;pow>>=1,(x*=x)%=p) if (pow&1) (res*=x)%=p;
	return res;
}

int rev[PN];

void FFT(int *a,int N,int f)
{
	for (int i=0;i<N;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (int i=1;i<N;i<<=1)
	{
		LL wn=Pow(gn,(f==1)?((PN/i)>>1):PN-((PN/i)>>1));
		for (int j=0;j<N;j+=(i<<1))
		{
			LL w=1;
			for (int k=0;k<i;k++,(w*=wn)%=p)
			{
				LL x=a[j+k],y=(LL)a[j+k+i]*w%p;
				a[j+k]=(x+y)%p,a[j+k+i]=(x-y+p)%p;
			}
		}
	}
	LL invN=Pow(N,p-2);
	if (f==-1) for (int i=0;i<N;i++) a[i]=(LL)a[i]*invN%p;
}

int tempA[PN],tempB[PN];

void Polynomial_Multyply(int *a,int *b,int n,int m,int *c)
{
	int N=1;
	while (N<n+m-1) N<<=1;
	for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
	for (int i=0;i<n;i++) tempA[i]=a[i];for (int i=n;i<N;i++) tempA[i]=0;
	for (int i=0;i<m;i++) tempB[i]=b[i];for (int i=m;i<N;i++) tempB[i]=0;
	for (int i=0;i<N;i++) c[i]=0;
	FFT(tempA,N,1);FFT(tempB,N,1);
	for (int i=0;i<N;i++) c[i]=(LL)tempA[i]*tempB[i]%p;
	FFT(c,N,-1);
}

void Polynomial_Inverse(int *a,int *inva,int n)
{
	if (n==1)
	{
		inva[0]=Pow(a[0],p-2);
		return;
	}
	int mid=(n+1)>>1,N=1;
	Polynomial_Inverse(a,inva,mid);
	while (N<(n<<1)) N<<=1;
	for (int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
	for (int i=0;i<n;i++) tempA[i]=a[i];
	for (int i=n;i<N;i++) tempA[i]=0;
	for (int i=0;i<mid;i++) tempB[i]=inva[i];
	for (int i=mid;i<N;i++) tempB[i]=0;
	FFT(tempA,N,1);FFT(tempB,N,1);
	for (int i=0;i<N;i++) inva[i]=(LL)((2-(LL)tempA[i]*tempB[i]%p+p)%p)*tempB[i]%p;
	FFT(inva,N,-1);
	for (int i=n;i<N;i++) inva[i]=0;
}

int f[PN],a[PN],b[PN],invb[PN],A[PN],B[PN],C[PN],invB[PN];

int main()
{
	int n;
	scanf("%d",&n);
	for (int i=0;i<=n;i++) a[i]=Pow(2,(LL)i*(i-1)/2);
	b[0]=1;
	for (int i=1;i<=n;i++) b[i]=(LL)b[i-1]*i%p;
	for (int i=0;i<=n;i++) invb[i]=Pow(b[i],p-2);
	for (int i=0;i<n;i++) B[i]=(LL)a[i]*invb[i]%p;
	for (int i=0;i<n;i++) C[i]=(LL)a[i+1]*invb[i]%p;
	Polynomial_Inverse(B,invB,n);
	Polynomial_Multyply(C,invB,n,n,f+1);
	printf("%d\n",(LL)f[n]*b[n-1]%p);
	return 0;
}