【置换群】CH Round #63

zhouerla

　　第一问置换群裸题。
　　第二问单独考虑某个循环，任意交换两个元素，稍微画一下就会发现，把该循环拆成了2个，剩下所需的交换次数减少了1，也就是说，第一步我们任意交换，都能够保证交换次数最少。于是一个循环的答案就是n*(n-1)/2，把所有的加起来即可。
　　进而我们发现，在剩下的步骤里面，我们只需在拆出来的两个循环里任意交换即可。



#include<cstdio>
using namespace std;
#define N 50001
bool vis[N];
int n,op,a[N],sumv,sum2;
int main()
{
scanf("%d%d",&n,&op);
for(int i=1;i<=n;++i) scanf("%d",&a);
for(int i=1;i<=n;++i)
if(!vis)
{
vis=1;
int cnt=1;
int U=a;
while(U!=i)
{
vis[U]=1;
U=a[U];
++cnt;
}
sumv+=(cnt-1);
sum2+=(cnt*(cnt-1)>>1);
}
if(op==1)
printf("%d\n",sumv);
else
printf("%d\n%d\n",sumv,sum2);
return 0;
}