AGC031D A Sequence of Permutations

AGC031D

有个排列的数列，(a_1=p)，(a_2=q)。

(f(p,q))表示第(p_i)个数为(q_i)的排列，即(f(p,q)_{p_i}=q_i)

(a_n=f(a_{n-2},a_{n-1}))

问第(a_k)是多少。

(nle 10^5,kle 10^9)

---

一开始思考的时候置换的定义姿势不对……直接把题目的那个操作定义为置换的乘法了……

我们如此定义置换：(f=pq)，即(f_i=p_{q_i})

那么(a_n=a_{n-1}a_{n-2}^{-1})

把前面若干项写出来，会发现一个规律：设(A=qp^{-1}q^{-1}p)，则(a_n=Aa_{n-6}A^{-1})。可以归纳证明。

算出(A)的若干次方。可以直接快速幂，也可以把轮换找出来直接移动。

---

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
int n,k;
int p[N],q[N],p_[N],q_[N],A[N];
void inv(int p_[],int p[]){
	static int r[N];
	for (int i=1;i<=n;++i)
		r[p[i]]=i;
	memcpy(p_,r,sizeof(int)*(n+1));
}
void multi(int f[],int p[],int q[]){
	static int r[N];
	for (int i=1;i<=n;++i)
		r[i]=p[q[i]];
	memcpy(f,r,sizeof(int)*(n+1));
}
void getpow(int p[],int k){
	static int vis[N],r[N],q[N];
	memset(vis,0,sizeof(int)*(n+1));
	for (int i=1;i<=n;++i)
		if (!vis[i]){
			int cnt=0;
			for (int x=i;!vis[x];x=p[x])
				vis[x]=1,q[cnt++]=x;
			for (int j=0;j<cnt;++j)
				r[q[j]]=q[(j+k)%cnt];
		}
	memcpy(p,r,sizeof(int)*(n+1));
}
int main(){
	freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i)
		scanf("%d",&p[i]);
	for (int i=1;i<=n;++i)
		scanf("%d",&q[i]);
	inv(p_,p),inv(q_,q);
	memcpy(A,q,sizeof(int)*(n+1));	
	multi(A,A,p_),multi(A,A,q_),multi(A,A,p);
	int r=(k-1)%6;
	for (int i=0;i<r;++i){
		inv(p,p);
		multi(p,q,p);
		swap(p,q);
	}
	getpow(A,(k-1)/6);
	multi(p,A,p);
	inv(A,A);
	multi(p,p,A);
	for (int i=1;i<=n;++i)
		printf("%d ",p[i]);
	return 0;
}