http://codeforces.com/problemset/problem/484/C

题目意思比较难描述。。所以自己看吧。。。

 

假设前面的一段操作对于的置换是 P。再定义把字符串左移一个位置对应置换 L，右移对应 R。

那么这个操作可以看做是：$$(L^0 P R^0) (L^1 P R^1) (L^2 P R^2) ... (L^{n-l}PR^{n-l})$$

也就是：$$P(LP)^{n-l}R^{n-l}$$

 

模拟置换的乘法复杂度是 $O(n)$。于是可以利用快速幂来求最终置换。

 

$P.S.$ memset 太多 TLE 了一回 0.0

#include 
     
      typedef std::vector
      
        Replace;typedef const Replace& CR;typedef Replace& Rf;void multiply(CR a, CR b, Rf result){  int n = (int) a.size();  for (int i = 0; i < n; i++)    result[i] = b[a[i]];}Replace mulTmp;void multiply(Rf a, CR b){  multiply(a, b, mulTmp);  for (int i = 0; i < (int) a.size(); i++)    a[i] = mulTmp[i];}void power(Rf a, int p, Rf result){  for (int i = 0; i < (int) result.size(); i++)    result[i] = i;  for (; p; p >>= 1) {    if (p & 1)      multiply(result, a);    multiply(a, a);  }}Replace powTmp;void power(Rf a, int p){  power(a, p, powTmp);  for (int i = 0; i < (int) a.size(); i++)    a[i] = powTmp[i];}const int MAXN = 1000000 + 5;char str[MAXN];char res[MAXN];Replace P, L, LP, R, T;int main(){  scanf("%s", str);  int n = strlen(str);  L.resize(n);  R.resize(n);  P.resize(n);  LP.resize(n);  T.resize(n);  mulTmp.resize(n);  powTmp.resize(n);  for (int i = 0; i < n; i++)    T[i] = i;  int m;  scanf("%d", &m);  for (int l, d; m--; ) {    scanf("%d %d", &l, &d);    for (int i = 0; i < n; i++) {      L[i] = i - 1;      R[i] = i + 1;    }    L[0] = n - 1;    R[n - 1] = 0;    for (int i = 0; i < n; i++)      P[i] = i;    int now = 0;    for (int i = 0; i < d; i++) {      for (int j = i; j < l; j += d)        P[j] = now++;    }    multiply(L, P, LP);    power(LP, n - l);    power(R, n - l);    multiply(T, P);    multiply(T, LP);    multiply(T, R);    memset(res, 0, sizeof(char) * (n + 1)); // sizeof(res) will TLE.    for (int i = 0; i < n; i++)      res[T[i]] = str[i];    puts(res);    // strcpy(str, res);  }  return 0;}// 0 1 2 3 4 5// 0 1 0 1 4 5// 0 2 1 3 4 5