每个城市到达其他城市的路径都是有向的。
不存在两个城市可以互相到达。
这个国家的元首现在很愤怒，他大喊一声"气死偶咧！"，然后决定把所有的路径都毁掉再重建。
元首想知道有多少种重建的方案使得这个国家仍然奇葩。
题解思路
设 表示当前 个点构成的 DAG 数量。
删掉出度为零的点后图依然是个 DAG，因此我们可以枚举出度为零的点的个数，得到：
但是我们这样枚举出来的是至少有 个出度为零的点，因此我们使用广义容斥定理乘上容斥系数，最终答案为：
边界条件：
参考代码
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=3e3,p=1e9+7;
int c[N+10][N+10],f[N+10];
int mlt(int a,int b){
int res=1;
for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
return res;
}
int main(){
int n=read();
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])%p;
}
f[0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
f[i]=(f[i]+1ll*(j&1?1:-1)*c[i][j]*mlt(2,j*(i-j))%p*f[i-j]%p)%p;
printf("%d\n",(f[n]+p)%p);
return 0;
}
时间复杂度
，对于 完全可行。
暂无评论