Codeforces 484C Strange Sorting(置換)

Codeforces 484C Strange Sorting(置換)

題目鏈接：Codeforces 484C Strange Sorting

題目大意：給定一個長度為N的字符串，現在有M次詢問，每次要從左向右逐個對長度為K的子串進行D-sorting，最後

輸出生成的串。

解題思路：問題即為一個置換的思想，L對應的左移一位的置換，C對應的是D-sorting前K為的置換，每次執行完一次C

肯定執行一下L，保證D-sorting的為不同的K長度子串。用類似矩陣快速冪的思想對字符串進行求解，最後在有循環移

動對應的N-K位。

#include 
#include 
#include 

using namespace std;
const int maxn = 1e6+5;

int N, M, K, D, L[maxn];
int C[maxn], P[maxn], x[maxn], tmp[maxn];
char str[maxn];

void multi () {
    for (int i = 0; i < N; i++) tmp[i] = x[x[i]];
    for (int i = 0; i < N; i++) x[i] = tmp[i];
}

int main () {
    scanf("%s%d", str, &M);
    N = strlen(str);
    for (int i = 0; i < N; i++)
        L[i] = (i ? i - 1 : N - 1);

    while (M--) {
        scanf("%d%d", &K, &D);

        for (int i = 0; i < N; i++) C[i] = i;
        int mv = 0;
        for (int i = 0; i < D; i++) {
            for (int j = i; j < K; j += D)
                C[j] = mv++;
        }
        for (int i = 0; i < N; i++) P[i] = C[i];
        for (int i = 0; i < N; i++) x[i] = C[L[i]];

        int n = N - K;
        while (n) {
            if (n&1) {
                for (int i = 0; i < N; i++)
                    P[i] = x[P[i]];
            }
            multi();
            n >>= 1;
        }

        for (int i = 0; i < N; i++) tmp[P[i]] = str[i];
        for (int i = 0; i < N; i++) str[(i + (N - K)) % N] = tmp[i];
        printf("%s\n", str);
    }
    return 0;
}