CodeForces 711D Directed Roads

时间:2022-12-28 20:11:02

计数,模拟。

首先观察一下给出的图的特点:

$1.$一定存在环。

$2.$可能存在多个环。

我们对每个环计算方案数,假设环$C$上包含$x$条边,那么把环$C$破坏掉的方案数有${2^x} - 2$种。

那么答案就是每个环的方案数乘起来,再乘上${2^p}$,$p$表示不在环上的边的条数。

找环的话模拟一下就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-; const int maxn=;
int n,a[maxn],cnt;
int f[maxn],g[maxn],sz;
LL b[maxn],ans=;
LL mod=1e9+; int main()
{
b[]=;
for(int i=;i<=;i++) b[i]=(*b[i-])%mod; scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]); for(int i=;i<=n;i++)
{
if(f[i]!=) continue; int now=i,p=; f[i]=p; sz++; g[i]=sz;
while()
{
if(f[a[now]]==)
{
p++; f[a[now]]=p;
g[a[now]]=sz;
now=a[now];
}
else
{
if(g[a[now]]==sz)
{
cnt=cnt+f[now]-f[a[now]]+;
ans=(ans*((b[f[now]-f[a[now]]+]-+mod)%mod))%mod;
}
break;
}
}
} ans=ans*b[n-cnt]%mod;
printf("%lld\n",ans); return ;
}