A1738 Chino的数列

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s, m;
    unsigned long long k;
    cin >> n >> s >> m >> k;
    --s;
    --m;
    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    // 一组操作 = 先交换 a_s、a_m，再整体左移一位。
    // 把它看成位置上的置换 pi：新的第 i 位 = 旧的第 pi(i) 位。
    //   pi(i) = tau((i+1) mod n)，tau 是 (s m) 交换。
    const int LOG = 64;
    vector<vector<int>> pw(LOG, vector<int>(n));
    for (int i = 0; i < n; i++) {
        int t = (i + 1) % n;
        if (t == s) t = m;
        else if (t == m) t = s;
        pw[0][i] = t;
    }
    for (int b = 1; b < LOG; b++)
        for (int i = 0; i < n; i++)
            pw[b][i] = pw[b - 1][pw[b - 1][i]];

    vector<int> cur(n);
    for (int i = 0; i < n; i++) cur[i] = i;
    for (int b = 0; b < LOG; b++)
        if ((k >> b) & 1ULL)
            for (int i = 0; i < n; i++) cur[i] = pw[b][cur[i]];

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << a[cur[i]];
    }
    cout << "\n";
    return 0;
}