[BZOJ2863:]愤怒的元首

Description

Pty生活在一个奇葩的国家，这个国家有n个城市，编号为1~n。
每个城市到达其他城市的路径都是有向的。
不存在两个城市可以互相到达。
这个国家的元首现在很愤怒，他大喊一声“气死偶咧！”，然后决定把所有的路径都毁掉再重建。
元首想知道有多少种重建的方案使得这个国家仍然奇葩。

Input

第一行一个整数：n

Output

输出n个城市的重建方案数mod(10^9+7)的结果

Hint：基图不连通也是合法方案

Sample Input

3

Sample Output

25

HINT

n <= 3000

---

题解

带标号的(DAG)计数
(f[i])表示有i个点的(DAG)的个数
那么如果去掉度数为0的点
这个(DAG)还是一个(DAG)
所以我们可以枚举有多少个度数为0的点
那么 (f[i] = f[i - j] * C(i , j) * 2 ^ {j * (i - j)})
但是实际上(f[i - j])的方案数也不都是度数都不为0
所以我们枚举的这个j表示的意义是至少有j个度数为0的点
所以还要再乘上一个容斥系数((-1)^{j-1})

代码

#include<cstdio>
const int M = 3005 ;
const int mod = 1e9 + 7 ;
using namespace std ;

int n , pw[M * M] , f[M] , c[M][M] ;
int main() {
	scanf("%d",&n) ;
	c[0][0] = 1 ;
	for(int i = 1 ; i <= n ; i ++) {
		c[i][0] = 1 ;
		for(int j = 1 ; j <= i ; j ++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod ;
	}
	f[0] = 1 ; pw[0] = 1 ; for(int i = 1 ; i <= n * n ; i ++) pw[i] = (pw[i - 1] * 2) % mod ;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= i ; j ++)
		    f[i] = (f[i] + (((j % 2) ? 1LL : -1LL) * 1LL * (1LL * f[i - j] * pw[j * (i - j)]) % mod * c[i][j]) % mod + mod) % mod ;
	printf("%d
",(f[n] + mod) % mod) ;
	return 0 ;
}