[JZOJ3303] 【集训队互测2013】城市规划

题目

题目大意

求\(N\)个点的简单无向图的方案数（有编号）。

结果对\(1004535809\)取模。

---

思考历程

感觉这个问题非常经典。

当时想到了一堆式子，但都觉得可能会有重和漏，于是弃掉了……

最终打了个纯得不能再纯的暴力，在本地开O3，将\(1\)到\(8\)的答案都跑出来，打了个表……

---

正解

正解的一部分似乎被我错过了。

显然是DP，设\(f_i\)表示大小为\(i\)的连通图个数，\(g_i\)表示大小为\(i\)的所有图的个数。

显然\(g_i=2^{C_n^2}\)

接下来是转移：用总体情况减去不连通的情况。对于不连通的情况，我们固定\(i\)不动，\(i\)在一个大小为\(j\)的连通块内，剩下的\(i-j\)个点以任意方式排列，但就是不与\(i\)所在的连通块相连。

综上所述，\(f_i=g_i-\sum_{j=1}^{i-1}C_{i-1}^{j-1}f_jg_{i-j}\)

为什么不重，为什么不漏？

直觉告诉我这是个感性理解的东西……不好用语言描述啊……

接下来化一下式子：\(f_i=g_i-(i-1)!\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\frac{g_{i-j}}{(i-j)!}\)

设\(F_i=\frac{f_i}{(i-1)!} \ G_i=\frac{g_i}{i!}\)，\(H_i=\sum_{j=1}^{i-1}F_jG_{i-j}\)

我们发现这是一个卷积的形式！

然后就是一个分治FFT（NTT）……（当然我之前不会）

不过实际上思想也比较简单，就是用CDQ分治的思想，用左边的东西计算对右边的贡献。

具体来说，用\([l,mid]\)影响\([mid+1,r]\)，

也就是\((F_l,F_{l+1},...,F_{mid})\)乘上\((G_1,G_2,...,G_{r-l})\)。注意位置的对应关系……（想当初这东西调了我很久）

时间复杂度自然是\(O(n\lg^2 n)\)的。

当然，这道题用NTT当然更好。因为FFT有可怕的精度问题啊……

\(1004535809\)是NTT的模数，原根为\(3\)。取\(n\)次单位根的时候就直接\(3^\frac{mo-1}{n} \mod mo\)就是了。

NTT和FFT几乎一模一样，具体的理论部分，我想我就懒得涉猎了……

---

代码

可能和我讲的不太一样。在分治之前，我开到了\(2\)的幂……但似乎没个卵用……

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define PI 3.14159263538979
#define mo 1004535809
#define N 131073
long long my_pow(long long x,long long y){
long long res=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
res=res*x%mo;
return res;
}
int n,m;
long long fac[N],inv[N];
long long f[N],g[N],h[N];
int M;
long long a[N*4],b[N*4],c[N*4];
int rev[N*4];
inline void ntt(long long*a,int flag){
for (int i=0;i<M;++i)
if (i<rev[i])
swap(a[i],a[rev[i]]);
for (int i=1;i<M;i<<=1){
long long wn=my_pow(3,(mo-1)/(i*2));
if (flag==-1)
wn=my_pow(wn,mo-2);
for (int j=0;j<M;j+=i<<1){
long long wnk=1;
for (int k=j;k<j+i;++k,wnk=wnk*wn%mo){
long long x=a[k],y=wnk*a[k+i]%mo;
a[k]=(x+y)%mo;
a[k+i]=(x-y+mo)%mo;
}
}
}
long long invM=my_pow(M,mo-2);
if (flag==-1)
for (int i=0;i<M;++i)
a[i]=a[i]*invM%mo;
}
inline void calc(){
for (int i=0;i<M;++i){
int tmp=0;
for (int j=i,k=0;1<<k<M;j>>=1,++k)
tmp=tmp<<1|j&1;
rev[i]=tmp;
}
ntt(a,1),ntt(b,1);
for (int i=0;i<M;++i)
c[i]=a[i]*b[i];
ntt(c,-1);
}
void dfs(int l,int r){
if (l==r){
f[l]=(g[l]-h[l]%mo*fac[l-1]%mo+mo)%mo;
return;
}
int mid=l+r>>1;
dfs(l,mid);
for (M=1;M<=3*(mid-l);M<<=1);
memset(a,0,sizeof(long long)*M);
memset(b,0,sizeof(long long)*M);
for (int i=0;i<mid-l+1;++i)
a[i]=f[l+i]*inv[l+i-1]%mo;
for (int i=0;i<mid-l+mid-l+1;++i)
b[i]=g[i+1]*inv[i+1]%mo;
calc();
for (int i=mid-l;i<mid-l+mid-l+1;++i)
h[l+i+1]+=c[i];
dfs(mid+1,r);
}
int main(){
scanf("%d",&n);
fac[0]=1,inv[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo,inv[i]=my_pow(fac[i],mo-2);
for (int i=1;i<=n;++i)
g[i]=my_pow(2,1ll*i*(i-1)>>1);
for (m=1;m<n;m*=2);
dfs(1,m);
printf("%lld\n",f[n]);
return 0;
}


---

总结

DP能力还是要加强啊……