# AT4694 题解
题目传送门 AT4694
我的原 blog
(LaTeX 不显示，凑活看吧。。。)
# 题意简述
给定两个排列，使其满足要求。
# 题目分析
这种题一般来说都会先上来枚举找一找规律，先列上八个找找看呀！
a1=p
a2=q
a_3=qp^
a_4=qp^{-1}q^
a_5=qp^{-1}q^{-1}pq^
a_6=qp^{-1}q^{-1}p^2q^
a_7=qp^{-1}q^{-1}pqpq^
a_8=qp^{-1}q^{-1}pqp^{-1}qpq^
列着列着，诶？怎么发现了什么？没错，规律出来了！计算通项就是 an=bab−1, 其中 b=qp−1q−1p。
知道了结论，我们还是比较容易归纳证明的：显然 bb−1=e (e 为单位元，ei=i)。
于是设 n′=m−6m′, an=bm′an′b−m′。
我们之后就可以开心的写快速幂的代码啦！
# 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
#define int long long
#define rint register int
using namespace std;
int p[1000005],q[1000005],pp[1000005],qq[1000006],g[1000005],f[1000005],ff[1000005],tmp[1000005],aux[1000005],cnt[1000005],a[10][1000005],n,m;
signed main(){
cin>>n>>m;
for(rint i=1;i<=n;i++)
{
cin>>p[i];
pp[p[i]] = i;
}
for(rint i=1;i<=n;i++)
{
cin>>q[i];
qq[q[i]] = i;
}
for(rint i=1;i<=n;i++)
{
a[1][i]=p[i];
a[2][i]=q[i];
}
for(rint k=3;k<=6;k++)
for(rint i=1;i<=n;i++)
a[k][a[k-2][i]]=a[k-1][i];
for(rint i=1;i<=n;i++)
{
g[i]=q[pp[qq[p[i]]]];
f[i]=i;
tmp[i]=g[i];
}
int nn=m%6==0?6:m%6;
m=(m-1)/6;
for(rint i=0;m!=0;i++)
{
if(m&(1<<i))
{
m-=(1<<i);
for(rint j=1;j<=n;j++)
aux[j]=f[tmp[j]];
for(rint j=1;j<=n;j++)
f[j]=aux[j];
}
for(rint j=1;j<=n;j++)
aux[j]=tmp[tmp[j]];
for(rint j=1;j<=n;j++)
tmp[j]=aux[j];
}
for(rint i=1;i<=n;i++)
ff[f[i]]=i;
for(rint i=1;i<=n;i++)
cnt[i]=f[a[nn][ff[i]]];
for(rint i=1;i<=n;i++)
cout<<cnt[i]<<" ";
puts("");
}
|
