Subtask 1: ~k=1~

• Sử dụng ~map~.

• Đặt ~mp[a[i]] = b[i]~ với ~∀ i ∈ [0,25]~. Sau đó với ~s[i]~ in ra ~mp[s[i]]~.

• ĐPT: ~O(n*log(26))~

Subtask 2: ~k,|s|≤2000~

• Tạo map ~mp~ tương tự subtask 1, sau đó với mọi ~s[i]~ thì gán ~s[i] = mp[s[i]]~ ~k~ lần, sau đó in ra sâu ~s~.

• ĐPT: ~O(n*k*log(26))~

Subtask 3: ~k≤10^5~

• Nhận thấy, nếu làm như subtask 2, sẽ có trường hợp một kí tự bị duyệt nhiều lần, vậy nên tạo mảng ~f[x] = x~ với ~x~ là các kí tự từ a đến z. Gán ~f[x] = mp[f[x]]~ ~k~ lần. Với ~s[i]~ in ra ~f[s[i]]~.

• ĐPT: ~O(n + k*26*log(26))~

Subtask 4: ~k≤10^9~

• Việc for ~(1 → k)~ là không đủ nhanh. Nhận thấy nếu liên tục gán ~x = mp[x]~ thì sẽ xảy ra vòng lặp (khi ~x~ quay về kí tự ban đầu). Cải tiến: tạo vector ~c[i]~ là các phần tử trong "vòng lặp" của kí tự ~i~. Gọi ~sz~ là kích cỡ của vector ~c[i]~. Ta có: ~f[i] = c[i][k~ % ~sz]~.

• ĐPT: ~O(n+26*log(26))~

Code tham khảo:

//lamleloi
namespace sub4
{
    vector<int> c[26];
    map<char,char> mp,f;
    void sol()
    {
        for(int i=0; i<26; i++) mp[a[i]] = b[i];
        for(int i=0; i<26; i++){
            c[i].push_back(i);
            char cur = mp['a'+i];
            while(cur-'a'!=i) {
                c[i].push_back(cur-'a');
                cur = mp[cur];
            }
        }
        for(int i=0; i<26; i++){
            int pos = k%(c[i].size());
            f['a'+i] = c[i][pos] + 'a';
        }
        for(int i=0; i<s.size(); i++) cout << f[s[i]];
    }
}