题解：AT_abc380_d [ABC380D] Strange Mirroring

Lumira · 2024-11-22 16:44:12 · 题解

目前洛谷最优解。

题意简述

对于一个给定的字符串 S 反复执行将每一位字母大小写交换后放入 S 尾部的操作，求进行足够多次操作后第 k 位的字符。

分析

暴力模拟自然是不行的。

由于每一次操作都会使长度变成原来的两倍，所以我们考虑可能结果与二进制有关。然后我们发现对于第 t 遍重复，其是否翻转与 t 中字符 1 的奇偶性有关。下面给出证明：

我们记首次字符串为第 0 次。以下位置指的是单位串在总串中的位置，而非单个字符组成的字符串。易知，首次字符串处于未翻转状态。我们记现在的次数的位数为 0。每一次进行操作，都是将现有的每一个次数增大 1 后复制到末尾。而我们注意到，每一次操作新建的字符串位置恰为每个复制前的位置的二进制前加上 1。由于第一数学归纳法，第 n 位字符串翻转次数为 n 的二进制展开中 1 的数量。G++ 有内建函数 __builtin_popcount 可用于求位 1 出现次数和 __builtin_parity 可用于求 1 的数目的奇偶性，这两个函数效率都非常高。

注意要在两个函数末尾加 ll 以将参数改成 unsigned long long。

于是得出代码。

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(void)
{
    static T ans=0;
    static char ch;
    ans=0;
    do{ch=getchar();}while(!isdigit(ch));
    do{ans*=10;ans+=ch-'0';}while(isdigit(ch=getchar()));
    return ans;
}
inline constexpr char rev(char c)
{
    if(c<='Z')c+='a'-'A';
    else c-='a'-'A';
    return c;
}
int main()
{
    char str[200007];
    long long q,k,len;
    scanf("%s",str);
    q=read<long long>();
    len=strlen(str);
    while(q--)
    {
        k=read<long long>();
        k--;
        long long r=k/len;
        if(__builtin_parityll(r))
        putchar(rev(str[k-r*len]));
        else
        putchar(str[k-r*len]);
        putchar(' ');
    }
    return 0;
}