bzoj 3456 城市规划

Posted on | Edited on | Views:

多项式求逆.

要求的是带标号的 $n$ 个点的无向连通图数目.

设 $f(i)$ 表示 $i$ 个点时的答案,可以用图的总数减去不连通的图的数目.

枚举 $1$ 号节点所在连通块的大小为 $i$ 进行转移.
$$
f(n)=2^{n\choose 2}-\sum_{i=1}^{n-1} {n-1\choose i-1}\cdot f(j)\cdot 2^{n-i\choose 2}
$$
边界有 $f(1)=1​$ .

为了进行优化,考虑将 $f(n)$ 这一项也弄到 $\sum$ 里面去.可以两边乘上 $\frac {1}{(n-1)!}$ ,整理得到,
$$
\frac{f(n)}{(n-1)!}+\sum_{i=1}^{n-1} \frac{f(i)\cdot 2^{n-i\choose 2}}{(i-1)!(n-i)!}=\frac{2^{n\choose 2}}{(n-1)!}
$$
规定 $f(0)=0$ ,就可以把 $f(n)$ 也弄进去了,对比可以验证正确性.
$$
\sum_{i=0}^{n} \frac{f(i)\cdot 2^{n-i\choose 2}}{(i-1)!(n-i)!}=\frac{2^{n\choose 2}}{(n-1)!}
$$
等式左边是一个卷积的形式,设三个多项式 $A,B,C$ 分别为
$$
A(x)=\sum_{i} \frac{f(i)}{(i-1)!} \cdot x^i \\
B(x)=\sum_{i}\frac{2^{i\choose 2}}{i!} \cdot x^i \\
C(x)=\sum_{i} \frac{2^{i\choose 2}}{(i-1)!} \cdot x^i
$$
则有 $A(x)B(x)=C(x)$ ,而 $C(x)$ 的最高次数为 $n$ .

于是
$$
A(x)\equiv B^{-1}(x)\cdot C(x) \pmod {x^{n+1}}
$$
用多项式求逆解决,时间复杂度 $O(n\log n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int P=1004535809,G=3;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL *a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=8e5+10;
int rev[MAXN],omega[MAXN],inv[MAXN],curn=0;
void init(int n)
{
	if(curn==n)
		return;
	for(int i=0;i<n;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
	for(int l=2;l<=n;l<<=1)
	{
		omega[l]=fpow(G,(P-1)/l);
		inv[l]=fpow(omega[l],P-2);
	}
	curn=n;
}
void DFT(int *a,int n,bool invflag)
{
	init(n);
	for(int i=0;i<n;++i)
		if(i<rev[i])
			swap(a[i],a[rev[i]]);
	for(int l=2;l<=n;l<<=1)
	{
		int m=l>>1;
		int gi=omega[l];
		if(invflag)
			gi=inv[l];
		for(int *p=a;p!=a+n;p+=l)
		{
			int g=1;
			for(int i=0;i<m;++i)
			{
				int t=mul(p[i+m],g);
				p[i+m]=add(p[i],P-t);
				p[i]=add(p[i],t);
				g=mul(g,gi);
			}
		}
	}
	if(invflag)
	{
		int invn=fpow(n,P-2);
		for(int i=0;i<n;++i)
			a[i]=mul(a[i],invn);
	}
}
void NTT(int *A,int *B,int *C,int lenA,int lenB)
{
	static int NTT_A[MAXN],NTT_B[MAXN];
	int lenC=lenA+lenB-1;
	int n=1;
	while(n<lenC)
		n<<=1;
	copy(A,A+lenA,NTT_A);
	fill(NTT_A+lenA,NTT_A+n,0);
	copy(B,B+lenB,NTT_B);
	fill(NTT_B+lenB,NTT_B+n,0);
	DFT(NTT_A,n,false);
	DFT(NTT_B,n,false);
	for(int i=0;i<n;++i)
		C[i]=mul(NTT_A[i],NTT_B[i]);
	DFT(C,n,true);
}
void PolyInverse(int *A,int *B,int N) // A^(-1)=B mod x^N
{
	int n=1;
	while(n<N)
		n<<=1;
	static int tmp[MAXN];
	fill(B,B+2*n,0);
	B[0]=fpow(A[0],P-2);
	for(int i=2;i<=n;i<<=1)
	{
		NTT(A,B,tmp,i,i);
		NTT(tmp,B,tmp,i,i);
		for(int j=0;j<i;++j)
			B[j]=add(mul(2,B[j]),P-tmp[j]);
	}
}
int n;
int fac[MAXN],invfac[MAXN];
int A[MAXN],B[MAXN],invB[MAXN],C[MAXN];
int main()
{
	n=read();
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[n]=fpow(fac[n],P-2);
	for(int i=n-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
	B[0]=1,C[0]=0;
	for(int i=1;i<=n;++i)
	{
		B[i]=mul(fpow(2,1LL*i*(i-1)/2%(P-1)),invfac[i]);
		C[i]=mul(fpow(2,1LL*i*(i-1)/2%(P-1)),invfac[i-1]);
	}
	PolyInverse(B,invB,n+1);
	NTT(invB,C,A,n+1,n+1);
	int ans=mul(A[n],fac[n-1]);
	cout<<ans<<endl;
	return 0;
}