CF711D-Directed Roads(组合数学 dfs找环)

CF711D-Directed Roads(组合数学 dfs找环)

​​linkkk​​

题意：

思路：

代码

// Problem: D. Directed Roads// Contest: Codeforces Round #369 (Div. 2)// URL: Memory Limit: 256 MB// Time Limit: 2000 ms// // Powered by CP Editor (namespace std;typedef long long ll;typedef unsigned long long ull;typedef pairPLL;typedef pairPII;typedef pairPDD;#define I_int llinline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}#define read read()#define rep(i, a, b) for(int i=(a);i<=(b);++i)#define dep(i, a, b) for(int i=(a);i>=(b);--i)ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}const int maxn=2e5+100;const ll mod=1e9+7;int n,a[maxn],siz[maxn],vis[maxn];vectorg[maxn];vectorw;void dfs(int u,int sum){ vis[u]=1; siz[u]=sum; for(auto t:g[u]){ if(!vis[t]) dfs(t,sum+1); else if(vis[t]==1){ w.push_back(siz[u]-siz[t]+1); } } vis[u]=2;}int main(){ n=read; rep(i,1,n){ g[i].push_back(read); } rep(i,1,n){ if(!siz[i]) dfs(i,1); } ll ans=1,tot=0; for(auto t:w){ tot+=t; ans=ans*(ksm(2,t,mod)-2+mod)%mod; } ans=ans*ksm(2,n-tot,mod)%mod; cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。