AGC008E Next or Nextnext 题解

设从

i

指向

p_i

所形成的图为

G_1

，从

i

指向

a_i

所形成的图为

G_2

，考虑考查

G_1

和

G_2

之间的关系。

显然

G_1

由若干个环组成，于是考虑

G_1

中的每一个环：

若环上的每一个点都满足 $a_i=p_i$ ，则 $G_2$ 中有一个一模一样的环；
若环上的每一个点都满足 $a_i=p_{p_i}$ 且环长为奇数，则 $G_2$ 中有一个环长相同但不一样的环；
若环上的每一个点都满足 $a_i=p_{p_i}$ 且环长为偶数，则 $G_2$ 中有两个环长为该环长度一半的环；
若环上既存在满足 $a_i=p_i$ 的点又存在满足 $a_i=p_{p_i}$ 的点，则 $G_2$ 中会存在一棵由一个环和若干条链组成的基环内向树。

接下来考虑

G_2

如何推回

G_1

。

先考虑

G_2

中的环。设

G_2

中有

c_i

个长度为

i

的环，枚举要合并的环的数量

2j

：

若 $j \ne 0$ $j \neq = 0$ ：
- 从 $cnt_i$ 个环中选出 $2j$ 个环，方案数为 $cnt_i \choose 2j$ ；
- 从 $2j$ 个环中选出左侧的 $j$ 个环，钦定左侧的环的顺序为 $1\sim j$ ，枚举右侧环的顺序，并去掉交换同一行两个环的方案，得到方案数为 $\frac{{2j \choose j}j!}{2^j}$ ；
- 每对环有 $i$ 种合并方式，方案数为 $i^j$ ；
若 $i$ 为奇数且 $i\ne1$ ，则每个不被合并的环也有 $2$ 种方案，方案数为 $2^{cnt_i-2j}$ ；

将每个步骤的方案数相乘即可得到这个部分的结果，将每个

j

的结果相加即可得到每种环长的答案。

再考虑

G_2

中的基环内向树。不妨设基环内向树的环上的点依次为

1,2,\dots,m

，其中对于每个不大于

n

的正整数

i

都存在一条从

(i \bmod m)+1

指向

i

的边；设挂着链的点依次为

p_1,p_2,\dots,p_k

，挂在

p_i

上的链的长度为

l_i

，则我们需要将

l_i

插回

p_i

到

p_{(i \bmod k)+1}

之间。设

p_i

到

p_{(i \bmod m)+1}

之间有

e

条边：

若 $e>l_i$ ，则插回的方案数为 $2$ ；
若 $e=l_i$ ，则插回的方案数为 $1$ ；
若 $e<l_i$ ，则插回的方案数为 $0$ 。

将每条链插回的方案数相乘即可得到这部分的结果，答案即为每个环和每棵基环内向树的方案数的乘积。

朴素实现的时间复杂度为

\mathcal O(n \log n)

，精细实现可以做到

\mathcal O(n)

。

const int N=1e5+5,mod=1e9+7;
int n,a[N],c[N],vis[N],ans=1,fac[N<<1],infac[N<<1];
vector <int> ve[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1,a=1ll*a*a%mod; 
	}
	return res;
}
int C(int n,int m){
	return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void dfs(int u,bool f,int len){
	f|=(ve[u].size()!=1);
	vis[u]=1,len++;
	if(vis[a[u]]){
		if(!f) return c[len]++,void();
		vector <int> s,p,l;
		s.pb(u),vis[u]=2;
		int v=a[u];
		while(v!=u) s.pb(v),vis[v]=2,v=a[v];
		int m=s.size();
		for(int i=0;i<m;i++){
			int u=s[i];
			if(ve[u].size()==2){
				if(vis[ve[u][0]]==2) v=ve[u][1];
				else v=ve[u][0];
				int cnt=0;
				while(1){
					vis[v]=1,cnt++;
					if(ve[v].size()==2) cout<<0<<endl,exit(0);
					if(ve[v].size()==0) break;
					v=ve[v][0];
				}
				p.pb(i),l.pb(cnt);
			}
		}
		int k=p.size();
		for(int i=0;i<k;i++){
			int e;
			if(i==0) e=p[i]+m-p[k-1];
			else e=p[i]-p[i-1];
			if(e>l[i]) add(ans,ans);
			if(e<l[i]) cout<<0<<endl,exit(0);
		}
		return;
	}
	dfs(a[u],f,len);
}
void solve(){
	cin>>n;
	fac[0]=infac[0]=1;
	for(int i=1;i<=n+n;i++) fac[i]=1ll*i*fac[i-1]%mod;
	infac[n+n]=ksm(fac[n+n],mod-2);
	for(int i=n+n-1;i>0;i--) infac[i]=1ll*(i+1)*infac[i+1]%mod;
	for(int i=1;i<=n;i++) cin>>a[i],ve[a[i]].pb(i);
	for(int i=1;i<=n;i++) if(ve[i].size()>2) cout<<0<<endl,exit(0);
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs(i,0,0);
	}
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=0;j+j<=c[i];j++){
			int res=1;
			if(j!=0) res=1ll*C(c[i],j+j)*C(j+j,j)%mod*fac[j]%mod*ksm((mod+1)/2,j)%mod*ksm(i,j)%mod;
			if((i&1)&&i!=1) res=1ll*res*ksm(2,c[i]-j-j)%mod;
			add(sum,res);
		}
		ans=1ll*ans*sum%mod;
	}
	cout<<ans<<endl;
}

AGC008E Next or Nextnext 题解

文章操作

相关推荐

评论

AGC008E Next or Nextnext 题解