//可以看出操作1和操作2是一对互逆操作
//即是一次操作1和一次操作2执行后，排列不变
//如果一种操作连续做i次能得到s
//如果i刚好等于k，puts("YES")
//如果不等，看剩下的k-i次操作能不能用一次操作1和一次操作2做完
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 110 ;
int p_h[maxn][maxn] ;
int p_t[maxn][maxn] ;
int s[maxn] ;
int q[maxn] ;
int n , k;
int t[maxn] ;
int main()
{
// freopen("input.txt","r",stdin) ;
while(~scanf("%d %d" ,&n , &k))
{
for(int i = 1;i <= n;i++)
scanf("%d" ,&q[i]),t[q[i]] = i ;
int flag = 0 ;
for(int i = 1;i <= n;i++)
{
scanf("%d" , &s[i]);
if(s[i] != i)
flag = 1;
}
if(!flag)
{
puts("NO") ;
continue ;
}
for(int i = 1;i <= n;i++)
p_h[0][i] = i,p_t[0][i] = i;
int pos_h = 0 ,pos_t = 0;
for(int i = 1;i <= k;i++)
{
int flag_h = 0 ,flag_t = 0 ;
for(int j = 1;j <= n;j++)
{
p_h[i][j] = p_h[i-1][q[j]] ;
if(p_h[i][j] != s[j])flag_h = 1;
p_t[i][j] = p_t[i-1][t[j]];
if(p_t[i][j] != s[j])flag_t = 1;
}
if(!flag_h && !pos_h)pos_h = i ;
if(!flag_t && !pos_t)pos_t = i;
}
if(pos_h == 1&&pos_t==1&&k > 1)
puts("NO") ;
else if(((k-pos_h)%2 == 0&&pos_h)||((k-pos_t)%2 ==0&&pos_t))
puts("YES") ;
else puts("NO") ;
}
return 0;
}
Codeforces Round #153 (Div. 1)BPlaying with Permutations
原文：http://blog.csdn.net/cq_pf/article/details/45315215
