[AGC031D] A Sequence of Permutations——置换、结论

众所周知排列和一个置换矩阵是等价的，所以我们不妨把排列 p , q p,q p,q 看成置换矩阵 P , Q P,Q P,Q。

首先可以从定义上得出 f ( P , Q ) = P T Q f(P,Q)=P^TQ f(P,Q)=PTQ，然后我们回顾一下基本公式（ A A T = A T A = E , ( A B ) T = B T A T AA^T=A^TA=E,(AB)^T=B^TA^T AAT=ATA=E,(AB)T=BTAT），开始手玩：
a 1 = P a 2 = Q a 3 = P T Q a 4 = Q T    P T    Q a 5 = Q T P    Q T    P T Q a 6 = Q T P    P Q T    P T Q a 7 = Q T P Q    P    Q T P T Q a 8 = Q T P Q P T    Q    P Q T P T Q a 9 = Q T P Q P T    P T Q    P Q T P T Q a 10 = Q T P Q P T Q T    P T    Q P Q T P T Q . . . a_1=P\ a_2=Q\ a_3=P^TQ\ a_4=Q^T,,P^T,,Q\ a_5=Q^TP,,Q^T,,P^TQ\ a_6=Q^TP,,PQ^T,,P^TQ\ a_7=Q^TPQ,,P,,Q^TP^TQ\ a_8=Q^TPQP^T,,Q,,PQ^TP^TQ\ a_9=Q^TPQP^T,,P^TQ,,PQ^TP^TQ\ a_{10}=Q^TPQP^TQ^T,,P^T,,QPQ^TP^TQ\ ... a1​=Pa2​=Qa3​=PTQa4​=QTPTQa5​=QTPQTPTQa6​=QTPPQTPTQa7​=QTPQPQTPTQa8​=QTPQPTQPQTPTQa9​=QTPQPTPTQPQTPTQa10​=QTPQPTQTPTQPQTPTQ...可以发现式子的中间部分是 P , Q , P T Q , P T , Q T , P Q T , P . . . P,Q,P^TQ,P^T,Q^T,PQ^T,P... P,Q,PTQ,PT,QT,PQT,P... 循环的，式子左右两边互为转置，而左边部分以 + 1 , + 1 , 0 +1,+1,0 +1,+1,0 规律变长，是 Q T P Q P T Q T P Q P T . . . Q^TPQP^TQ^TPQP^T... QTPQPTQTPQPT... 循环的。

所以只需要判断一下中间部分，然后左右两边快速幂即可。

#include//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=114514;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}

#define arr vector
int n,k,m;
arr P,Q,A,B,C;
arr tr(const arr&x){
	arr res(n+1,0);
	for(int i=1;i<=n;i++)res[x[i]]=i;
	return res;
}
arr operator*(const arr&a,const arr&b){
	arr res(n+1,0);
	for(int i=1;i<=n;i++)res[i]=b[a[i]];
	return res;
}
arr ksm(arr a,int b){
	arr res(n+1,0);
	for(int i=1;i<=n;i++)res[i]=i;
	for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
	return res;
}
int main()
{
	n=read(),k=read(),P.resize(n+1),Q.resize(n+1);
	for(int i=1;i<=n;i++)P[i]=read();
	for(int i=1;i<=n;i++)Q[i]=read();
	if(k%6==1)B=P;
	else if(k%6==2)B=Q;
	else if(k%6==3)B=tr(P)*Q;
	else if(k%6==4)B=tr(P);
	else if(k%6==5)B=tr(Q);
	else B=P*tr(Q);
	if(k<4)m=0;
	else m=k-3-(k-3)/3;
	A=ksm(tr(Q)*P*Q*tr(P),m>>2),m&=3;
	if(m>0)A=A*tr(Q);
	if(m>1)A=A*P;
	if(m>2)A=A*Q;
	C=A*B*tr(A);
	for(int i=1;i<=n;i++)print(C[i],i