关于此题[ABC367E] Permute K times倍增思想的一些总结

传送门
第一次接触到倍增思想是用来求lca时，为了避免一层一层往上爬浪费时间复杂度。再后来就是区间DP中一小类问题或者是部分图上问题可以用倍增来优化。
那么这道题其实可以看作图上问题来使用倍增优化。看到这道题的数据范围，K达到了\(10^{18}\)量级，这让我们不得不思考log级别往下复杂度的算法，又由于，每一次操作都相当于从当前节点走到下一个节点，可以看作在图上，每个i到x[i]连一条有向边，求的就是从每一个节点出发走K步能走到的节点。显然给出的图中必定存在环。我们只需要用f[u][i]表示从u节点出发走\(2^{i}\)步能走到的节点。时间复杂度\(O(nlogk)\)
代码如下：

#include<bits/stdc++.h>

using namespace std;

long long t;
const long long N = 2e5 + 10;
long long n,k;
long long x[N],a[N];
long long f[N][65];

void solve() {
    cin >> n >> k;
    for(long long i = 1;i <= n;i++) {
        cin >> x[i];
        f[i][0] = x[i];
    }
    for(long long i = 1;i <= n;i++) cin >> a[i];
    for(long long i = 1;i <= 64;i++)
        for(long long j = 1;j <= n;j++)
            f[j][i] = f[f[j][i-1]][i-1];
    for(long long i = 1;i <= n;i++) {
        long long u = i;
        for(int j = 0;j <= 62;j++) {
            long long t = pow(2,j);
            if((k & t) != 0) u = f[u][j];
        }
        cout << a[u] << ' ';
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    t = 1;
    while(t--) solve();

    return 0;
}

值得注意的是，由于$ << $运算符只能算到31位二进制，再多就会出错，所以这里用了pow