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

· · 题解

Solution:

算了一个小时求和没求出来，结果回头一看模数发现是诈骗啊啊啊！ 本题字符串要转为 26 进制后用十进制表示。我们从一个具体的字符串 S=\texttt{bcbcbc...bcbc} 开始研究：
从低位转换，第 1 位的权值是 26^0，第二位是 26^1，以此类推。此时发现题目中要求模 2^p，这个数似乎不太常见，联想数字 2，可以发现 26=2\times13，因此 26^n=2^n\times13^n，当 n\geq{p} 时，对应位数的权值模 2^p 都为 0，因此对总答案无贡献。也就是说，本题至多只需要计算前 20 位即可。
题做到这里，思路应当是先进行几次模拟直到位数大于等于 p 就停止，同时对类似 \texttt{aaaaab} 这类特殊情况作特殊处理。然而，这题数据实在是太水了，根本就不需要特判：
正确的代码不再放出，可以参考其他题解。
写这道题的时候，我首先写了一个不带任何特判、仅针对规模较大的数据的部分解，本来准备看看情况再修改，想不到居然过了。这里给出这种部分解，给出一种答题思路的参考： ::::info[对于本题数据较好写的部分解] 对于这题所给出的数据，另一个较好写的部分解是：
对于任意输入字符串，直接对其进行复制直到长度大于 p，然后截取尾端长度为 p 的字符串。当数据规模较大时即字符串长度长于 p，该结果保证正确，但在遇到如 S=\texttt{ab} 或 S=\texttt{c},k=1 这类数据时就需要特殊处理。做题时可以先做一般情况，结果正确后再做特殊情况。

AC Code:

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

int main(){
    string s;
    long long k,sum=0;
    int p,base0=1;
    cin >> k >> p >> s;
    while(s.size()<20) s=s+s;
    s=s.substr(s.size()-p,p);
    for(int i = s.size()-1;i>=0;--i){
        sum += base0*(s[i]-'a');
        base0*=26;
        base0%=(1<<p);
        sum%=(1<<p);
    }
    cout << sum%(1<<p) << endl;
    return 0;
}
//やり残した鼓動がこの夜を覆って

::::