[Codeforces] 711D. Directed Roads
題目連結:http://codeforces.com/problemset/problem/711/D
小品(?的圖論題。首先有個小觀察,這種給法的圖,在每一個連通塊(?中,只會有一個環,不過還是可能會有很多連通塊就是了。所以先考慮一個連通塊的情況,發現若他的環有$k$個邊,且整個連通塊有$n$個邊的話,他的方法數就會是$(2^k-2)\cdot(2^{n-k})$,想法大致就是,環上每個邊都可以選擇要換或不換扣掉全換跟全部換,再乘以其他大家的可能性就好了。至於多個連通塊的情況就直接把他們乘在一起就好了,畢竟他們是獨立的。
小品(?的圖論題。首先有個小觀察,這種給法的圖,在每一個連通塊(?中,只會有一個環,不過還是可能會有很多連通塊就是了。所以先考慮一個連通塊的情況,發現若他的環有$k$個邊,且整個連通塊有$n$個邊的話,他的方法數就會是$(2^k-2)\cdot(2^{n-k})$,想法大致就是,環上每個邊都可以選擇要換或不換扣掉全換跟全部換,再乘以其他大家的可能性就好了。至於多個連通塊的情況就直接把他們乘在一起就好了,畢竟他們是獨立的。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
#define FF first
#define SS second
const int N = 200000 + 5;
const lld MOD_BASE = 1e9 + 7;
class DJS{
private:
vector<int> arr, sz;
public:
void init(int n){
arr.resize(n);
sz.resize(n);
for(int i=0;i<n;i++){
arr[i]=i;
sz[i]=1;
}
}
int size(int x){return sz[query(x)];}
int query(int x){
if(arr[x]!=x) arr[x] = query(arr[x]);
return arr[x];
}
void merge(int a, int b){
if(size(a) < size(b)) swap(a, b);
int aa = query(a), bb = query(b);
if(aa==bb) return;
arr[aa]=bb;
sz[bb]+=sz[aa];
}
} djs;
vector<int> G[N];
int dfn[N];
bool done[N];
int dfs(int);
lld qPow(lld,int);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n; cin>>n;
djs.init(n+1);
for(int i=1;i<=n;i++){
int x; cin>>x;
G[i].PB(x);
djs.merge(x, i);
}
vector<lld> ans;
for(int i=1;i<=n;i++){
if(done[djs.query(i)]) continue;
dfn[i]=1;
int huan = dfs(i);
if(huan==0) continue;
ans.PB((((qPow(2, huan)-2+MOD_BASE)%MOD_BASE) * qPow(2, djs.size(i)-huan))%MOD_BASE);
dfn[i]=0;
done[djs.query(i)] = 1;
}
lld res = !ans.empty();
for(auto i: ans) res = (res*i)%MOD_BASE;
cout<<res<<'\n';
return 0;
}
int dfs(int x){
for(auto i: G[x]){
if(dfn[i] != 0) return dfn[x]+1-dfn[i];
dfn[i] = dfn[x]+1;
int ret = dfs(i);
dfn[i]=0;
if(ret!=0) return ret;
}
return 0;
}
lld qPow(lld a, int x){
lld ret = 1;
while(x){
if(x&1) ret = (ret*a)%MOD_BASE;
x>>=1;
a = (a*a)%MOD_BASE;
}
return ret;
}
留言
張貼留言