[BZOJ2863:]愤怒的元首

元首"/>

[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\n",(f[n] + mod) % mod) ;return 0 ;
}

转载于:.html