元首关键算法"/>
java实现统计元首关键算法
Description
Pty生活在一个奇葩的国家,这个国家有n个城市,编号为1~n。
每个城市到达其他城市的路径都是有向的。
不存在两个城市可以互相到达。
这个国家的元首现在很愤怒,他大喊一声“气死偶咧!”,然后决定把所有的路径都毁掉再重建。
元首想知道有多少种重建的方案使得这个国家仍然奇葩。
Input
第一行一个整数:n
Output
输出n个城市的重建方案数mod(10^9+7)的结果
Hint**:**基图不连通也是合法方案
Sample Input
3
Sample Output
25
HINT
n <= 3000
Source
题解
前置知识:容斥原理
题解
求$n$个点的$DAG$(有向无环图)的个数。
设$f(i)$为$i$个点的$DAG$的个数。
对于$n$个点的$DAG$的个数,考虑至少有$i$个入度为$0$的点的方案为: $$ f(n-i) \binom{n}{i} 2^{i(n-i)} $$ 可以考虑选出了$i$个点,剩下的点和选出的点随便连的方案数。
然后注意到恰好$0$个入度为$0$的点的方案数为$0$,由容斥原理可得: $$ \sum_{i=0}^{n} (-1)^{i} f(n-i) \binom{n}{i} 2^{i(n-i)}=0 $$ 移项可得: $$ f(n)=\sum_{i=1}^{n} (-1)^{i+1} f(n-i) \binom{n}{i} 2^{i(n-i)} $$
#include
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) x=-x,putchar('-');
if(!x) return ;print(x/10),putchar(x%10+'0');
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define maxn 10050
#define mod 1000000007
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=a*a%mod) if(x&1) res=res*a%mod;
return res;
}
int f[maxn],fac[maxn],ifac[maxn];
signed main() {
int n;read(n);fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=qpow(fac[n],mod-2);
for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
f[1]=f[0]=1;
for(int i=2;i<=n;i++)
for(int j=1,op=-1;j<=i;j++) op*=-1,f[i]=(f[i]+op*f[i-j]*qpow(2,j*(i-j))%mod*fac[i]%mod*ifac[i-j]%mod*ifac[j]%mod)%mod;
write((f[n]+mod)%mod);//cerr << (double)clock()/CLOCKS_PER_SEC << endl;
return 0;
}
更多推荐
java实现统计元首关键算法
发布评论