题目背景
译自 CCC 2025 Senior T2。本题满分为 15。
题目描述
给定一个小写字母组成的字符串 s 和一个非负整数 c。你需要求出,将这个字符串无限重复后,第 c 个位置上的字符是什么。注意字符串是 0−indexed 的,也就是 s0 是第一个字符。
为了减少输入量,我们将字符串做了压缩:具体地,我们将一段连续的相同字母 $\underbrace{\texttt{aa}\cdots\texttt{aa}}_{k\text{ 个}}$ 压缩成字母+出现次数 ak 的形式。例如,aaaabccdddd 被压缩成 a4b1c2d4。
输入格式
第一行,一个只含小写字母和数字的压缩后的字符串 s′。
第二行,一个非负整数 c。
输出格式
一个小写字母,表示答案。
r2d2
8
r
a4b1c2d10
100
d
提示
样例解释
- 样例 1 解释:r2d2 压缩前是 rrdd。
重复无数多次即为 rrddrrddrrdd⋯。
- 样例 2 解释:a4b1c2d10 压缩前是 aaaabccdddddddddd。
子任务
对于 100% 的数据,保证:
- 2≤∣s′∣≤105;
- s′ 中出现的整数的范围是 [1,1012];
- 0≤c≤1012。
- Subtask 0(0 points):样例。
- Subtask 1(6 points):
- 0≤c≤2×103;
- s′ 中出现的整数的范围是 [1,9];
- 压缩前,s 的长度不超过 2000。
- Subtask 2(3 points):
- 0≤c≤106;
- 压缩前,s 的长度不超过 106。
- Subtask 3(3 points):
- 压缩前,s 的长度不超过 106。
- Subtask 4(3 points):无特殊限制。