题解 CF711D 【Directed Roads】

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 */ ```