AT_abc380_d [ABC380D] Strange Mirroring

[ABC380D] Strange Mirroring

不算困难。

考虑倒推，思考当前位置 x 是从哪个位置变化过来的，显然只用找到第一个 2^k\ge x，那么 x 就是从 x-2^k 变换过来的。

所以，我们只用让 x 变换到 <n 的某个位置就结束，观看变化次数，如果是奇数那就大小写互换，如果是偶数那就不变。

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
#define int long long
#define DEBUG cout<<"when can get npy"<<endl;
int n;
char s[N];
signed main(){
    scanf("%s",s+1); n=strlen(s+1);
    int t; cin>>t;
    while(t--){
        int x;
        cin>>x;
        if(x<=n)    {cout<<s[x]<<' '; continue;}
        int dus=0;
        while(x>n){
            for(int i=0;i<=60;i++){
                __int128 now=(1ll<<i)*(__int128)n;
                if(now>=x){
                    int prelst=now/2+1;
                    x=(x-prelst+1);
                    dus++;
                    break;
                }
            }
        }
        if(dus%2==0)    cout<<s[x]<<' '; 
        else{
            if(s[x]>='A'&&s[x]<='Z')    cout<<(char)(s[x]-'A'+'a')<<' ';
            else    cout<<(char)(s[x]-'a'+'A')<<' ';
        }
    }
    return 0;
}