题目大意：求无向图的连通图个数。由于个数可能很大，只需要求出结果$mod1000000009$的值。$n\leq 1000$
-------------------------
对于一个含有$n$个结点的图，一共有$2^{\frac{n(n-1)}{2}}$种情况（把所有边连或不连都考虑到了，可以自行模拟出来）我们假设$h[n]=2^{\frac{n(n-1)}{2}}$。设$f[n]$表示大小为$n$的图的无向连通图个数。接下来我们假设图中有一个点$1$（叫什么都行）。
假设这个点只与$i-1$个点相连了。那么它们组成了一个大小为$i$的子图，方案数为$f[i]$。挑选方式有$C(n-1,i-1)$种。剩下还有$n-i$个点没有与这个子图联通，而它们之间的联通情况是随意的，即$h[n-i]$种。所以此时整个图不连通的情况有$C(n-1,i-1)*f[i]*h[n-i]$种。
因为$i$可以从$1$枚举到$n-1$，所以总的表达式有：
$h[n]=2^{\frac{n(n-1)}{2}}$
$f[n]=h[n]-\sum_{i=1}^{n-1} C(n-1,i-1)*f[i]*h[n-i]$
转移是$O(n)$的，快速幂$logn$。预处理$n^2$。
代码：
#include<bits/stdc++.h> using namespace std; const long long p=1e9+9; long long f[1005],h[1005],C[1005][1005]; int n; inline int qpow(int a,int b) { register long long ret=1; a%=p; for(;b;b>>=1,a=(long long)a*a%p) if(b&1) ret=ret*a%p; return ret; } int main() { cin>>n; for (int i=0;i<=n;i++) { C[i][0]=1; for (int j=1;j<=i;j++) C[i][j]=(long long)(C[i-1][j-1]+C[i-1][j])%p; } for (int i=1;i<=n;i++) h[i]=qpow(2,i*(i-1)/2); for (int i=1;i<=n;i++) { f[i]=h[i]; for (int j=1;j<i;j++) f[i]=(f[i]-(long long)C[i-1][j-1]*f[j]%p*h[i-j]%p+p)%p; f[i]=(f[i]+p)%p; } printf("%lld",f[n]); return 0; }