题解 CF711D 【Directed Roads】

2019-01-30 10:52:22


n条边 n个点

显然是基环树

由于不一定联通,可能有多个基环树

要求有向后不能有环

设每个环的点数为$w_i$

对于一条不在环上的边,方向随便取

总共$2^{n - \sum{wi}}$种方案

再考虑环上

对于一个有$w_i$个点的环

如 1 -- 2 -- 3 .... -- $w_i$ -- 1

( -- 表示边 , -> 和 <- 表示有向边) 那么 只有

1 -> 2 -> 3 .... -> $w_i$ -> 1

1 <- 2 <- 3 .... <- $w_i$ <- 1

这种连边方式会形成环,不合法

所以每一个环有 $2^{w_i} -2 $种方案

所以总方案就是

$2^{n - \sum{wi}} * \prod{2^{w_i} -2}$ 种方案

下面是代码

#include<bits/stdc++.h>
using namespace std;

#define MAXN 400005
#define LL long long
#define mo 1000000007 

int n,m;
int a[MAXN];
int c[MAXN];
struct aa
{
    int x,y,ls;
}b[MAXN];
int cnt;
int t[MAXN];
int h[MAXN];
int nn,mm; 

void jb(int x,int y)//建边 (建边的首字母不要误解)
{
    cnt ++;
    b[cnt].x = x;
    b[cnt].y = y;
    b[cnt].ls = t[x];
    t[x] = cnt;
} 

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

int an = 0;
void dfs(int x,int h)//找环
{
    if(c[x])
    {
        an =  h - c[x];
        return;
    }
    c[x] = h;
    dfs(a[x],h+1);
}

bool d[MAXN];

void dff(int x)
{
    d[x] = 1;
    for(int i = t[x]; i != 0; i = b[i].ls)
    {
        if(!d[b[i].y]) {
            dff(b[i].y); 
        }
    }
}

LL kasumi(LL x,LL y) {//快速幂(好像可以不用快速幂的)
    LL ans = 1;
    for( ; y > 0; x = x*x%mo, y >>= 1)
    if(y&1) ans = ans*x%mo;
    return ans;
}

int main()
{
    rd();
    m = 1;
    for(int i = 1; i <= n; i ++)
    {
        if(!d[i]) {
            dff(i);
            nn ++;
            an = 0;
            dfs(i,1);
            h[nn] = an;
            mm += h[nn];
        }
    }
    LL ans = kasumi(2,n - mm);
    for(int i = 1; i <= nn; i ++)
    {
        ans = ans*(kasumi(2,h[i]) - 2) %mo;
    } 
    cout<<ans;
    return 0;
} 
/*
6
2 3 2
5 4 5
*/