题解 AT4694 [AGC031D] A Sequence of Permutations

· · 题解

Atcoder 题面传送门 & 洛谷题面传送门

猜结论神题。

首先考虑探究题目中 f 函数的性质，f(p,q)_{p_i}=q_i\leftarrow f(p,q)\circ p=q，其中 \circ 为两个置换的复合，a\circ b 为满足 p_{i}=a_{b_i} 的置换 p，有点类似于函数的复合，u1s1 我一直把它当作乘法运算，因此总没搞清楚，心态爆炸……等式两边同乘 p 的复合逆 p^{-1} 可得 f(p,q)=q\circ p^{-1}。顺带一提复合满足性质 (p\circ q)^{-1}=q^{-1}\circ p^{-1}，这个对后面打表找规律有很大作用。

接下来考虑探究置换序列 a 的性质，我们不妨根据刚刚的性质先写出 a 的前几项看看瞧：

a_1=p a_2=q a_3=q\circ p^{-1} a_4=q\circ p^{-1}\circ q^{-1} a_5=q\circ p^{-1}\circ q^{-1}\circ p\circ q^{-1} a_6=q\circ p^{-1}\circ q^{-1}\circ p\circ p\circ q^{-1} \cdots

注意到这东西是一个类似于线性递推的东西，并且此题 k 高达 10^9，因此暴力推下去肯定是不行的，不过注意到相邻两项的 p,q 之间存在一些联系，具体来说，下一项实际上是对上一项进行如下变换：

那有人就问了，知道这个性质有什么用呢？你就算做了这样一个转化，还不照样还是要递推吗？

这里又有一个考验眼力的地方，注意到 a_5 中出现了一个式子叫做 q\circ p^{-1}\circ q^{-1}\circ p，我们不妨对其做一遍上面的变换，可得 (q\circ p^{-1})\circ q^{-1}\circ (p\circ q^{-1})\circ q，削消一下发现它就是 q\circ p^{-1}\circ q^{-1}\circ p，也就是说从 a_5 开始出现的 q\circ p^{-1}\circ q^{-1}\circ p 在变换前后不会发生变化，记 A=q\circ p^{-1}\circ q^{-1}\circ p，继续往下写几项可得：

a_5=A\circ q^{-1} a_6=A\circ p\circ q^{-1} a_7=A\circ q\circ p\circ q^{-1} a_8=A\circ q\circ p^{-1}\circ q\circ p\circ q^{-1}

发现了什么？p^{-1}\circ q\circ p\circ q^{-1} 就是 A^{-1}，因此 a_8 就等于 A\circ q\circ A^{-1}，按照上面的方式 a_7 也可变形为 A\circ p\circ A^{-1}。

A,A^{-1}$ 在变换前后都可看作不动点，因此 $a$ 序列可以看作类周期性变化的，即 $a_n=A\circ a_{n-6}\circ A^{-1}

矩阵快速幂即可。

总之是一道考验眼力的猜结论神题。

const int MAXN=1e5;
int n,k;
struct perm{
    int a[MAXN+5];
    perm(){for(int i=1;i<=n;i++) a[i]=i;}
    perm operator *(const perm &rhs) const{
        perm ret;
        for(int i=1;i<=n;i++) ret.a[i]=a[rhs.a[i]];
        return ret;
    }
} p,q;
perm inv(perm x){
    perm ret;
    for(int i=1;i<=n;i++) ret.a[x.a[i]]=i;
    return ret;
}
perm qpow(perm x,int e){
    perm ret;
    for(;e;e>>=1,x=x*x) if(e&1) ret=ret*x;
    return ret;
}
int main(){
    scanf("%d%d",&n,&k);k--;perm ans;
    for(int i=1;i<=n;i++) scanf("%d",&p.a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&q.a[i]);
    perm A=q*inv(p)*inv(q)*p;
    if(k%6==0) ans=p;
    if(k%6==1) ans=q;
    if(k%6==2) ans=q*inv(p);
    if(k%6==3) ans=A*inv(p);
    if(k%6==4) ans=A*inv(q);
    if(k%6==5) ans=A*p*inv(q);
    ans=qpow(A,k/6)*ans*qpow(inv(A),k/6);
    for(int i=1;i<=n;i++) printf("%d ",ans.a[i]);
    return 0;
}