CF1411F - The Thorny Path

题目大意

给定一个置换$p_i$，求通过最少次交换$p_i,p_j$，使得最终的置换中所有置换环$size$乘积最大


分析

一个常规结论：

对于$n(n\ge 3)$的拆分$n=\sum_{i=1}^m a_i$，最大化$\prod a_i$，最优情况下

1.$n\mod 3=0$，$a_i=3$

2.$n\mod 3=2$，$i<m,a_i=3 ; a_m=2$

3.$n\mod 3=1$，$i<m,a_i=3 ; a_m=4$或$i<m-1,a_i=3 ;a_{m-1}=a_m=2$

简要证明


容易发现对于任意$n$，最终$a_i$的方案是$O(1)$的，设当前置换环为$b_i$，我们需要操作$b_i$变成$a_i$

1.一次在同环交换可以分裂一个环

2.一次异环交换合并两个环

所以原问题实际上就是最少次数分裂合并$b_i$

对于$n\mod 3=0$或$n\mod 3=2$的情况，如果当前$b_i\ge 3$，可以一直不停分裂

最终剩下的就是$b’_i=1$或者$b’_i=2$

对于$n\mod 3=2$的情况，优先从中取出一个2<或者由两个1合并得到一个2

剩下的优先合并1和2，然后剩下的自己合并

$n\mod 3=1$同理，但是$a_i=4$的情况也不能分裂，需要拿出来特殊处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int N=1e6+10,P=1e9+7;

int n,m;
int Pow[N];
int A[N],L[N],C,R[N],D;
int vis[N];

int Calc(int c1,int c2){
	int t=min(c1,c2),ans=t;
	c1-=t,c2-=t;
	if(c1) ans+=c1/3*2;
	if(c2) ans+=c2;
	return ans;
}

int Calc(int c1,int c2,int c4){ return c4+Calc(c1+c4,c2); }

int main(){
	rep(i,*Pow=1,N-1) Pow[i]=1ll*Pow[i-1]*3%P;
	rep(_,1,rd()) {
		n=rd();
		rep(i,1,n) A[i]=rd(),vis[i]=0;
		C=0;
		rep(i,1,n) if(!vis[i]) {
			int c=0;
			for(int j=i;!vis[j];j=A[j]) c++,vis[j]=1;
			L[++C]=c;
		}
		if(n%3==0) {
			printf("%d ",Pow[n/3]);
			int ans=0;
			rep(i,1,C) {
				while(L[i]>3) L[i]-=3,ans++;
				if(L[i]==3) L[i]=0;
			}
			int c1=0,c2=0;
			rep(i,1,C) if(L[i]==1) c1++;
			else if(L[i]==2) c2++;
			ans+=Calc(c1,c2);
			printf("%d\n",ans);
			continue;
		}

		if(n%3==2) {
			printf("%d ",Pow[n/3]*2%P);
			int cnt=n/3,ans=0;
			rep(i,1,C) {
				while(cnt && L[i]>3) L[i]-=3,cnt--,ans++;
				if(L[i]==3 && cnt) L[i]=0,cnt--;
			}
			int c1=0,c2=0;
			rep(i,1,C) if(L[i]==1) c1++;
			else if(L[i]==2) c2++;
			if(c2) c2--;
			else c1-=2,ans++;
			ans+=Calc(c1,c2);
			printf("%d\n",ans);
			continue;
		}
		printf("%lld ",Pow[(n-4)/3]*4ll%P);
		int cnt=(n-4)/3,c3=0,ans=0;
		rep(i,1,C) {
			while(cnt && L[i]>4) L[i]-=3,cnt--,ans++;
			if(L[i]==3 && cnt) L[i]=0,cnt--;
		}
		int c1=0,c2=0,c4=0;
		rep(i,1,C) if(L[i]==1) c1++;
		else if(L[i]==2) c2++;
		else if(L[i]==3) c3++;
		else if(L[i]==4) c4++;
		if(c3) ans++;
		else {
			int w=1e9;
			if(c4) cmin(w,Calc(c1,c2,c4-1));
			if(c1>=4) cmin(w,Calc(c1-4,c2,c4)+2);
			if(c2>=2) cmin(w,Calc(c1,c2-2,c4));
			if(c1>=2 && c2)  cmin(w,Calc(c1-2,c2-1,c4)+1);
			ans+=w;
		}
		printf("%d\n",ans);
	}
}