题解：AT_abc367_e [ABC367E] Permute K times

Snoozing_QwQ · 2024-08-18 20:47:15 · 题解

题目大意：

给你两个长度为 n 的序列 X,A，每次操作将新的 A_i 设为旧的 A_{B_i}，求操作 m 次以后的序列

思路：

使用快速幂思路让 b 在 O(logm) 的复杂度得到可以让 A 一次变成结果的序列，每次乘法复杂度为 O(n) 总复杂度为 O(nlogm)，可以通过。\color{white}别问我为什么要在后面打句号

上代码 \sim，评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O1,O2,O3,O4,O5,Og,Os,Ofast,inline,-ffast-math")
//#define debug
int n,m;
struct QwQ{
    int length,a[200005];
    friend QwQ operator * (QwQ a,QwQ b){
        QwQ tmp;
        tmp.length = a.length;
        for(int i = 1;i<=a.length;i++) tmp.a[i] = b.a[a.a[i]];
        return tmp;
    }
    QwQ(int n){
        length = n;
        for(int i = 1;i<=n;i++) a[i] = i;
    }
    QwQ(){
        length = 0;
    }
}QAQ,AwA;
QwQ qmi(QwQ a, int k) {
    QwQ res(a.length);
    if(k==0) return res;
    if(k==1) return a;
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef debug

#endif
    cin >> n >> m;
    QAQ.length = n;
    for(int i = 1;i<=n;i++) cin >> QAQ.a[i];
    QAQ = qmi(QAQ,m);
    AwA.length = n;
    for(int i = 1;i<=n;i++) cin >> AwA.a[i];
    QAQ = QAQ*AwA;
    for(int i = 1;i<=n;i++) cout << QAQ.a[i] << " ";
    return 0;
}