### T1--强连通分量每个点仅有一条出边，因此图由多个基环树构成。每个基环树包含一个环，环外可能有树结构指向环上的节点。强连通分量只能是环本身，因为树结构的节点无法形成环。假设每个点在所有子集中独立构成一个强连通分量，每个点出现在 [imath:0]2^{n-1} [/imath:0]个子集中，故总和最大为[imath:0]n * 2^{n-1}[/imath:0]。对于每个长度为[imath:0]k[/imath:0]的环：初始计算将环中每个点视为独立贡献，导致多计算了 [imath:0]k-1[/imath:0] 次。当环的 [imath:0]k[/imath:0] 个点全被保留时，它们形成一个强连通分量，贡献为 [imath:0]1[/imath:0]，而非 [imath:0]k[/imath:0]。因此需减去 [imath:0](k-1) * 2^{n-k}[/imath:0]，其中 [imath:0]2^{n-k}[/imath:0] 是其他点的选择方式数目。对于自环（[imath:0]a_i = i[/imath:0]）的长度为 k=1，调整项为 [imath:0](1-1) * 2^{n-1} = 0[/imath:0]，无需修正。综上所述，假设图中第 [imath:0]i[/imath:0] 个环中点的个数为 [imath:0]k_i[/imath:0] 个，则答案为 [math:0]n*2^{n-1}-\sum(k-1)*2^{n-k}[/math:0] #### code： ```cpp #include #define int long long using namespace std; const int mod=1e9+7; const int N=1e6+5; int n,a[N],din[N],huan[N],cnt,v[N]; void dfs(int x){ int nx=a[x]; if(!v[nx]){ din[nx]=din[x]+1; v[nx]=1; dfs(nx); } else if(v[nx]==1&&din[nx]!=0){ huan[++cnt]=din[x]-din[nx]+1; } v[x]=2; } int qpow(int a,int b,int p){ int ans=1; while(b){ if(b&1) ans=(ans*a)%p; a=(a*a)%p; b>>=1; } return ans; } signed main(){ cin>>n; for(int i=1;i

【NOIP模拟赛】--二十二题解

Yichen

T1--强连通分量

每个点仅有一条出边，因此图由多个基环树构成。每个基环树包含一个环，环外可能有树结构指向环上的节点。强连通分量只能是环本身，因为树结构的节点无法形成环。假设每个点在所有子集中独立构成一个强连通分量，每个点出现在 2^{n-1} 个子集中，故总和最大为n * 2^{n-1}。

对于每个长度为k的环：初始计算将环中每个点视为独立贡献，导致多计算了 k-1 次。当环的 k 个点全被保留时，它们形成一个强连通分量，贡献为 1，而非 k。因此需减去 (k-1) * 2^{n-k}，其中 2^{n-k} 是其他点的选择方式数目。

对于自环（a_i = i）的长度为 k=1，调整项为 (1-1) * 2^{n-1} = 0，无需修正。

综上所述，假设图中第 i 个环中点的个数为 k_i 个，则答案为
n*2^{n-1}-\sum(k-1)*2^{n-k}

code：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mod=1e9+7;
const int N=1e6+5;
int n,a[N],din[N],huan[N],cnt,v[N];
void dfs(int x){
	int nx=a[x];
	if(!v[nx]){
		din[nx]=din[x]+1;
		v[nx]=1;
		dfs(nx);
	}
	else if(v[nx]==1&&din[nx]!=0){
		huan[++cnt]=din[x]-din[nx]+1;
	}
	v[x]=2;
}
int qpow(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return ans;
} 
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) if(!v[i]) dfs(i);
	int tot=(n%mod)*qpow(2,n-1,mod)%mod;
	for(int i=1;i<=cnt;i++){
		int k=huan[i];
		int ttt=(k-1)*qpow(2,n-k,mod)%mod;
		tot=(tot-ttt+mod)%mod;
	}
	cout<<tot%mod;
	return 0;
}

T2 原神

~~输出0可得5分（雾）~~

T3--叶子

~~太难了不会~~

T4 石子合并

~~同T3~~