大(NOIP模拟赛Round #10)

时间:2022-12-17 11:17:13

题目描述:

小Z有个n个点的高清大图,每个点有且只有一条单向边的出边。现在你可以翻转其中的一些边,使他从任何一个点都不能通过一些道路走回这个点。为了方便,你只需输出方案数对大(NOIP模拟赛Round #10)取模即可。当在两个方案中有任意同一条边的方向不同,这两个方案视为不同。

————————————————我是分割线————————————————

这道题目显然是结论题

我们知道这道题只要把每一个环破坏掉就行了,然后我们考虑破坏一个环的方案数,假设一个环有n条边,那么方案数为:

C(1,n)+C(2,n)+...+C(n-1,n)因为如果不翻转或者全部翻转那么都是环,不能满足题意

然后我们考虑不是环的边,显然他们翻不翻转都不影响答案。假设有m条边不属于环,那么方案数为

C(0,n)+...+C(n,n)

由于我们知道公式

C(0,n)+...+C(n,n)=2^n

所以我们就能轻松得出结果啦

#include<cstdio>
#define MN 200005
#define mod 1000000007
using namespace std;
int n,x,root=-1,dfsn,num,tt,total;
int fis[MN],head[MN],rudu[MN];
int huan[MN];
bool visit[MN];
long long ans=1;
struct edge{
int to,next;
}g[MN];
void ins(int u,int v){g[++num].next=head[u];head[u]=num;g[num].to=v;}
long long mi(int now){
long long tmp=2,res=1;
while(now){
if(now&1)res=(res*tmp)%mod;
now
>>=1;
tmp
=(tmp*tmp)%mod;
}
return res;
}
void dfs(int u){
if(fis[u]){
huan[
++tt]=dfsn-fis[u]+1;
return;
}
fis[u]
=++dfsn;
for(int i=head[u];i;i=g[i].next){
if(!visit[g[i].to])dfs(g[i].to),visit[g[i].to]=true;
}
}
int main(){
scanf(
"%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&x),ins(i,x);
for(int i=1;i<=n;i++)if(!visit[i])dfs(i),visit[i]=true;
for(int i=1;i<=tt;i++)ans=(ans*(mi(huan[i])-2+mod)%mod)%mod,total+=huan[i];
total
=n-total;
ans
=(ans*mi(total))%mod;
printf(
"%lld\n",ans);
}