[CSP-X 2023 山东] 克隆机

知识点

分段计数、倍增、整除定位

解题思路

放入机器的种子序列依次是每种1个、每种2个、每种4个……每轮k个字母各重复block次。若n超过本轮k*block个，就减去这整轮并令block翻倍；否则用(n-1)/block定位到本轮的字母。

正确性说明

每种种子取出一次会在队尾加入两个同类种子，因此完整处理一轮后，下一轮同一字母连续出现次数恰好翻倍，字母顺序不变。跳过的整轮长度和块内除法都由此精确计数。

易错点

n从1开始，定位前减1；k=1时始终为A；不能真的模拟10^18次；64位整数覆盖本题需要的轮长。

复杂度

时间O(log n)，额外空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){long long k,n;cin>>k>>n;long long block=1;while(n>k*block){n-=k*block;block*=2;}cout<<char('A'+(n-1)/block)<<'\n';}