题解：P16339 「WAOI Round 4.5」无尽循环

Build_Dreams · 2026-04-20 14:24:22 · 题解

前言

AK 啦！我真牛）

思路

诈骗诈骗诈骗诈骗诈骗诈骗诈骗。

注意到最后的形式一定是原本的字符串重复出现。

然后你发现这个 2^p 这个模数很诡异啊，你考虑设原串的数字值是 t，最后重复了 x 次，字符串长度是 len，那么最后的数值就是 \sum\limits_{k=0}^{x-1}t \cdot 26^{k \cdot len}，然后你发现 26 是一个偶数诶，所以只要 k \cdot len \ge p，模 2^p 就是 0 啊。

诶那我们来看一眼样例解释，我们发现单个字母 c 他操作两次 repeat 之后长度达到了 108 > p_{max} = 20！于是我们再往前。我们发现 b 在操作任意次数过后都是 b，而 a 操作一次过后就是空串。

那么判掉这两种情况，我们处理一下 repeat 一次的情况，对于别的就直接重复 p 次求就可以了。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 5;
int k, p; string s;

int qpow(int a, int b){
    int res = 1;
    while (b){
        if (b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p, b >>= 1;
    }
    return res;
}
int get(string s){
    int ans = 0;
    for (int i = 0; i < s.size(); i ++ ) ans = (26ll * ans + s[i] - 'a');
    return ans;
}
int get_mod(string s){
    int ans = 0;
    for (int i = 0; i < s.size(); i ++ ) ans = (26ll * ans + s[i] - 'a') % (1 << p);
    return ans;
}

signed main(){
    cin >> k >> p >> s;

    if (s == "b"){
        cout << 1 % (1 << p) << "\n";
    }
    else{
        bool flag = true;
        for (auto i : s)
            if (i != 'a'){
                flag = false;
                break;
            }
        if (flag){
            cout << "0\n";
        }
        else{
            if (k == 1){
                int t = get(s);
                if (t > p){
                    string tmp = s;
                    for (int i = 1; i < p; i ++ ) s += tmp;
                    cout << get_mod(s) % (1 << p);
                }
                else{
                    string tmp = s;
                    for (int i = 1; i < t; i ++ ) s += tmp;
                    cout << get_mod(s) % (1 << p) << '\n';
                }
            }
            else{
                string tmp = s;
                for (int i = 1; i < p; i ++ ) s += tmp;
                cout << get_mod(s) % (1 << p) << "\n";
            }
        }
    }
}