AtCoder Grand Contest 031 (AGC031) D - A Sequence of Permutations 其他

原文链接https://www.cnblogs.com/zhouzhendong/p/AGC031D.html

前言

比赛的时候看到这题之后在草稿纸上写下的第一个式子就是

$$f(p,q) = pq^{-1}$$

然后就再也没有改过。

发现了一堆奇奇怪怪的性质可是一直没有用。

直到官方题解出来的时候：

$$\Huge f(p,q) = qp^{-1}$$

题解

我们可以把前面的几个 $a_i$ 写出来。

$$\begin {eqnarray*}a_1 &=& p\\a_2 &=& q\\ a_3 &=& qp^{-1} \\ a_4 &=& qp^{-1} q^{-1}\\ a_5&=&qp^{-1}q^{-1}pq^{-1}\\a_6&=&qp^{-1}q^{-1}ppq^{-1}\\a_7&=&qp^{-1}q^{-1}pqpq^{-1}\\a_8&=&qp^{-1}q^{-1}pqp^{-1}qpq^{-1}\end{eqnarray*}$$

设

$$A = qp^{-1}q^{-1}p$$

则可以归纳证明：

$$\forall i>6, a_i = Aa_{i-6} A^{-1}$$

于是直接算一下置换 $A$ 的复合幂就好了。

算复合幂只要写成轮换的形式就可以做到时间复杂度 $O(n)$ ，我偷懒写了 $O(n\log n)$ 的快速幂。

代码

#pragma GCC optimize("Ofast","inline")

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

#define For(i,a,b) for (int i=a;i<=b;i++)

#define Fod(i,b,a) for (int i=b;i>=a;i--)

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\

						For(_v2,L,R)printf("%d ",a[_v2]);puts("");

using namespace std;

typedef long long LL;

typedef vector <int> vi;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=100005;

int n,k;

vi p,q,ip,iq,a[10];

vi Inv(vi A){

	vi B(n);

	For(i,0,n-1)

		B[A[i]]=i;

	return B;

}

vi Mul(vi A,vi B){

	vi C(n);

	For(i,0,n-1)

		C[i]=A[B[i]];

	return C;

}

vi Pow(vi x,int y){

	vi ans;

	For(i,0,n-1)

		ans.pb(i);

	for (;y;y>>=1,x=Mul(x,x))

		if (y&1)

			ans=Mul(ans,x);

	return ans;

}

int main(){

	n=read(),k=read();

	For(i,1,n)

		p.pb(read()-1);

	For(i,1,n)

		q.pb(read()-1);

	ip=Inv(p),iq=Inv(q);

	a[1]=p,a[2]=q;

	For(i,3,6)

		a[i]=Mul(a[i-1],Inv(a[i-2]));

	int len=(k-1)/6;

	vi cir=Pow(Mul(q,Mul(ip,Mul(iq,p))),len);

	vi rem=a[k-len*6];

	vi res=Mul(cir,Mul(rem,Inv(cir)));

	For(i,0,n-1)

		printf("%d ",res[i]+1);

	return 0;

}