【题目来源】
洛谷：P3612 [USACO17JAN] Secret Cow Code S - 洛谷（luogu.com.cn)
【题目描述】
奶牛们正在实验秘密代码，并设计了一种方法用于生成无限长度的字符串，作为他们代码的一部分。
给定一个字符串 \(s\)，令 \(F(s)\) 为 \(s\) 后接 \(s\) 向右“旋转”一个字符的结果（在右旋转中，\(s\) 的最后一个字符旋转并成为新的第一个字符）。给定初始字符串 \(s\)，奶牛们通过重复应用 \(F\) 来构建他们的无限长度代码字符串；因此每一步都会使当前字符串的长度翻倍。
给定初始字符串和一个索引 \(N\)，请帮助奶牛计算无限代码字符串中第 \(N\) 个位置的字符。
【输入】
输入由一行组成，包含一个字符串和 \(N\)。字符串最多由 30 个大写字母组成，且 \(N \leq 10^{18}\)。
请注意，\(N\) 可能太大，无法放入标准的 32 位整数中，因此你可能需要使用 64 位整数类型（例如，C/C++ 中的 "long long"）。
【输出】
请输出从初始字符串构建的无限代码字符串的第 \(N\) 个字符。第一个字符的位置为 \(N=1\)。
【输入样例】
COW 8
【输出样例】
C
【核心思想】
-
问题分析：给定初始字符串 \(s\)，通过不断应用 \(F(s) = s + rotate\_right(s)\) 构造无限长字符串（每次长度翻倍）。给定位置 \(N\)（\(N \leq 10^{18}\)），求该位置的字符。本质上是递归定位 + 逆向推导问题：利用字符串生成的对称性，从最终长度逆向缩回到初始字符串的对应位置。
-
算法选择：
- 逆向推导：不构造无限字符串，而是从目标位置 \(N\) 出发，逆向追踪其在初始字符串中的对应位置
- 长度倍增分析：每次操作后长度为 \(len \times 2\)，后半部分由前半部分右旋一位得到
-
关键步骤：
- 读取数据：读入字符串 \(s\) 和位置 \(N\)
- 计算覆盖长度：\(len1 = |s|\)，\(len2 = len1\)，不断 \(len2 \times 2\) 直到 \(len2 \geq N\)
- 逆向定位（当 \(N > len1\)）：
- \(k = len2 / 2 + 1\)（后半部分的起始位置）
- 若 \(N \geq k\)：
- 若 \(N = k\)（恰好是分割点），\(N \leftarrow N - 1\)（对应前半部分的最后一个字符）
- 否则 \(N \leftarrow N - k\)（映射到前半部分的对应位置）
- \(len2 \leftarrow len2 / 2\)（回退到上一阶段）
- 输出 \(s[N-1]\)（字符串 \(0\)-based 索引）
-
时间/空间复杂度：
- 时间复杂度：\(O(\log N)\)，每次循环长度减半
- 空间复杂度：\(O(1)\)，仅使用常数额外空间
-
逆向推导的核心思想：
- 生成规则的对称性：\(F(s) = s + s'\)，其中 \(s'\) 是 \(s\) 右旋一位的结果，即 \(s'[i] = s[(i-1) \bmod |s|]\)
- 后半部分的映射：若 \(N\) 在后半部分（\(N > len2/2\)），则 \(N\) 对应前半部分的 \(N - len2/2\) 位置，但需考虑右旋的偏移
- 分割点的特殊处理：\(k = len2/2 + 1\) 是后半部分的第一个位置，对应前半部分的最后一个字符（因右旋），故 \(N = k\) 时映射到 \(k-1\)
- 对数级复杂度：每次迭代长度减半，\(10^{18}\) 最多约 \(60\) 次迭代，完全可接受
- 适用于无限序列定位、递归映射、大数处理类问题
【解题思路】
【算法标签】
普及- #字符串入门
【代码详解】
#include <bits/stdc++.h>
using namespace std;int main()
{string s; // 初始字符串long long len1; // 初始字符串长度long long len2; // 扩展后的字符串长度long long n; // 要查询的位置long long k; // 中间变量，用于计算分割点cin >> s >> n; // 输入初始字符串和查询位置len1 = s.length(); // 获取初始长度len2 = len1; // 初始化扩展长度// 计算字符串扩展后的最小长度，使其包含位置nwhile (len2 < n)len2 *= 2; // 每次长度翻倍// 逆向计算原始字符串中对应的字符位置while (n > len1){k = len2 / 2 + 1; // 计算中间分割点if (n >= k) // 如果在后半部分{if (n == k) // 正好是分割点n--; // 调整到前一个位置elsen = n - k; // 调整到前半部分的对应位置}len2 /= 2; // 长度减半，回到上一阶段}// 输出结果（注意字符串从0开始索引）cout << s[n - 1];return 0;
}
【运行结果】
COW 8
C