题解 CF711D 【Directed Road】
Hexarhy
2021-03-19 21:39:50
### Preface
虽说是基环树，但感觉零基础人思考起来还是蛮容易的。
可以当作图论简单思维题~~基环树味淡~~。
### Solution
**慢慢读题很重要。** 稍微熟悉的话不难发现给定的是一个基环树。
对于一个 $n$ 条边的连通子图中，节点数为 $t$ 的环，能成环的方案只能是所有边指向同一方向，也就是只有 $2$ 种方案会形成环，即合法方案数为 $2^t-2$。
剩下的边方向就随意，方案数为 $2^{n-t}$。
那么一个连通子图的总方案就为 $2^{n-t}(2^t-2)$
每个连通子图都是互不影响的，那么整张图的方案数显然为：
$$\prod 2^{n_i-t_i}(2^{t_i}-2)$$
把其中一项提出来就可以得到大部分题解的式子：
$$2^{n-\sum t_i}\prod(2^{t_i}-2)$$
快速幂计算即可。
### Code
```cpp
void dfs(cint u,cint depth)//常见的找环方法
{
dep[u]=depth;
visit[u]=1;
for(const auto& v:edge[u])
{
if(!visit[v]) dfs(v,depth+1);
else if(visit[v]==1) ring.emplace_back(dep[u]-dep[v]+1);//记录环的大小
}
visit[u]=2;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
edge[i].emplace_back(x);
}
for(int i=1;i<=n;i++)
if(!dep[i]) dfs(i,1);
cint sum=accumulate(ring.begin(),ring.end(),0);//计算 sigma ti
for(const auto& t:ring) res=res*(qpow(2,t)-2+MOD)%MOD;
ll ans=res*qpow(2,n-sum)%MOD;
cout<<ans<<endl;
return 0;
}
```