题解 UVA306 【Cipher】

rui_er · 2021-09-24 21:44:57 · 题解

题意：多测，给你一个置换 A，分别对几个字符串 s_i 执行 k_i 次，问最后得到的字符串是啥。

我们知道两个置换的乘法：假设有置换 f=\begin{pmatrix}a_1 & a_2 & \cdots & a_n\\a_{p_1} & a_{p_2} & \cdots & a_{p_n}\end{pmatrix} 和 g=\begin{pmatrix}a_{p_1} & a_{p_2} & \cdots & a_{p_n}\\a_{q_1} & a_{q_2} & \cdots & a_{q_n}\end{pmatrix}，有 f\circ g=\begin{pmatrix}a_1 & a_2 & \cdots & a_n\\a_{q_1} & a_{q_2} & \cdots & a_{q_n}\end{pmatrix}。

我们可以用这个乘法运算代替整数乘法实现快速幂，即可在 O(n\log{k}) 的时间复杂度内求出 A^k。然后注意这个结果是一个置换，要知道最后第 i 个位置是几，就要看第二行为 i 的是第几个位置，输出对应字符即可。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
using namespace std;
typedef long long ll;
const int N = 205; 

int n, k;
template<typename T> void chkmin(T &x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T &x, T y) {if(x < y) x = y;}
struct Array {
    int p[N];
    Array() {memset(p, 0, sizeof(p));}
    Array(int n) {rep(i, 1, n) p[i] = i;}
    ~Array() {}
    friend Array operator * (const Array& a, const Array& b) {
        Array ans = Array(n);
        rep(i, 1, n) ans.p[i] = a.p[b.p[i]];
        return ans;
    }
    friend Array operator ^ (Array a, int k) {
        Array ans = Array(n);
        for(;k;k>>=1,a=a*a) if(k & 1) ans = ans * a;
        return ans;
    }
}a, b, c;

int main() {
    while(scanf("%d", &n) == 1 && n) {
        rep(i, 1, n) scanf("%d", &a.p[i]);
        while(scanf("%d", &k) == 1 && k) {
            string s;
            getline(cin, s); // there is a leading ' '
            rep(i, 1, n) s = s + ' ';
            b = a ^ k;
            rep(i, 1, n) c.p[b.p[i]] = i;
            rep(i, 1, n) printf("%c", s[c.p[i]]);
            puts("");
        }
        puts("");
    }
    return 0;
}