CodeForces 711D Directed Roads

计数，模拟。

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

$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-8;

const int maxn=200010;
int n,a[maxn],cnt;
int f[maxn],g[maxn],sz;
LL b[maxn],ans=1;
LL mod=1e9+7;

int main()
{
    b[0]=1;
    for(int i=1;i<=200000;i++) b[i]=(2*b[i-1])%mod;

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        if(f[i]!=0) continue;

        int now=i,p=1; f[i]=p; sz++; g[i]=sz;
        while(1)
        {
            if(f[a[now]]==0)
            {
                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]]+1;
                    ans=(ans*((b[f[now]-f[a[now]]+1]-2+mod)%mod))%mod;
                }
                break;
            }
        }
    }

    ans=ans*b[n-cnt]%mod;
    printf("%lld
",ans);

    return 0;
}