Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <vector>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- vector<int> operator*(const vector<int>& perm, const vector<int>& perm2) {
- const int N = perm.size();
- vector<int> answer;
- answer.reserve(N);
- for (int i = 0; i < N; ++i) answer.push_back(perm2[perm[i]]);
- return answer;
- }
- vector<int> power(const vector<int>& perm, int P) {
- const int N = perm.size();
- if (P == 0) { // return identity
- vector<int> ans(N);
- for (int i = 0; i < N; ++i) ans[i] = i;
- return ans;
- }
- if (P % 2 == 0) return power(perm*perm, P/2);
- return perm*power(perm*perm, P/2);
- }
- void trans(vector<int>& inic, int times) {
- const int N = inic.size();
- vector<bool> count(N, false);
- for (int t = 0; t < times; ++t) {
- int which = -1;
- for (int i = 0; i < N; ++i) if (!count[inic[i]]) {which = i; break;}
- count[inic[which]] = true;
- int temp = inic[which];
- int newPos = (which+t+1)%N;
- if (newPos < which) memmove(&inic[newPos+1], &inic[newPos], (which-newPos)*sizeof(int));
- else memmove(&inic[which], &inic[which+1], (newPos - which)*sizeof(int));
- inic[newPos] = temp;
- }
- }
- char buf[100];
- int main() {
- for (int _ = 0; ; _++) {
- int T;
- scanf("%d", &T);
- if (!T) break;
- printf("%d. ", _+1);
- scanf(" %s", buf);
- int N = strlen(buf);
- vector<int> perm(N);
- for (int i = 0; i < N; ++i) perm[i] = i;
- trans(perm, N);
- perm = power(perm, T/N);
- trans(perm, T%N);
- for (int i = 0; i < N; ++i) printf("%c", buf[perm[i]]);
- printf("\n");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment