Codeforces 484C Strange Sorting(置换) - c++编程基础

题目大意：给定一个长度为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; }