题目

Description

求n个点的dag个数。

Solution

设 f i f_i fi​为 i i i个点的 d a g dag dag个数。
至少有 i i i个入度为 0 0 0的点的方案为： f n − i ( i n ) 2 i ∗ ( n − i ) f_{n−i}(^n_i)2^{i*(n−i)} fn−i​(in​)2i∗(n−i)
容斥一下，则： f n = ∑ i = 1 n ( − 1 ) i − 1 f n − i ( i n ) 2 i ∗ ( n − i ) f_n=\sum_{i=1}^{n}(−1)^{i−1}f_{n−i}(^n_i)2^{i*(n−i)} fn​=∑i=1n​(−1)i−1fn−i​(in​)2i∗(n−i)

Code

#include<cstdio>
const int N=3002,M=1e9+7;
int n,bin[N*N/4],f[N],c[N][N],i,j;
int main(){
	scanf("%d",&n);
	for (i=bin[0]=f[0]=1;i<=n*n/4;i++) bin[i]=(bin[i-1]<<1)%M;
	for (i=0;i<=n;i++)
		for (j=1,c[i][0]=1;j<=i;j++)
	f[i]=(f[i]+1ll*(j&1?1:-1)*f[i-j]*(c[i][j]=(c[i-1][j]+c[i-1][j-1])%M)%M*bin[j*(i-j)]+M)%M;
	printf("%d",f[n]);
}