Guest User

Untitled

a guest
Oct 22nd, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <string.h>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. vector<int> operator*(const vector<int>& perm, const vector<int>& perm2) {
  8.     const int N = perm.size();
  9.     vector<int> answer;
  10.     answer.reserve(N);
  11.     for (int i = 0; i < N; ++i) answer.push_back(perm2[perm[i]]);
  12.     return answer;
  13. }
  14.  
  15. vector<int> power(const vector<int>& perm, int P) {
  16.     const int N = perm.size();
  17.     if (P == 0) { // return identity
  18.         vector<int> ans(N);
  19.         for (int i = 0; i < N; ++i) ans[i] = i;
  20.         return ans;
  21.     }
  22.     if (P % 2 == 0) return power(perm*perm, P/2);
  23.     return perm*power(perm*perm, P/2);
  24. }
  25.  
  26. void trans(vector<int>& inic, int times) {
  27.     const int N = inic.size();
  28.     vector<bool> count(N, false);
  29.     for (int t = 0; t < times; ++t) {
  30.         int which = -1;
  31.         for (int i = 0; i < N; ++i) if (!count[inic[i]]) {which = i; break;}
  32.         count[inic[which]] = true;
  33.         int temp = inic[which];
  34.         int newPos = (which+t+1)%N;
  35.         if (newPos < which) memmove(&inic[newPos+1], &inic[newPos], (which-newPos)*sizeof(int));
  36.         else memmove(&inic[which], &inic[which+1], (newPos - which)*sizeof(int));
  37.         inic[newPos] = temp;
  38.     }
  39. }
  40.  
  41. char buf[100];
  42. int main() {
  43.     for (int _ = 0; ; _++) {
  44.         int T;
  45.         scanf("%d", &T);
  46.         if (!T) break;
  47.         printf("%d. ", _+1);
  48.         scanf(" %s", buf);
  49.         int N = strlen(buf);
  50.         vector<int> perm(N);
  51.         for (int i = 0; i < N; ++i) perm[i] = i;
  52.         trans(perm, N);
  53.         perm = power(perm, T/N);
  54.         trans(perm, T%N);
  55.         for (int i = 0; i < N; ++i) printf("%c", buf[perm[i]]);
  56.         printf("\n");
  57.     }
  58.     return 0;
  59. }
Add Comment
Please, Sign In to add comment