#P11858. [CCC 2025 Senior] 破译 / Cryptogram Cracking Club

[CCC 2025 Senior] 破译 / Cryptogram Cracking Club

题目背景

译自 CCC 2025 Senior T2。本题满分为 1515

题目描述

给定一个小写字母组成的字符串 ss 和一个非负整数 cc。你需要求出,将这个字符串无限重复后,第 cc 个位置上的字符是什么。注意字符串是 0indexed\text{0}-\text{indexed} 的,也就是 s0s_0 是第一个字符。

为了减少输入量,我们将字符串做了压缩:具体地,我们将一段连续的相同字母 $\underbrace{\texttt{aa}\cdots\texttt{aa}}_{k\text{ 个}}$ 压缩成字母+出现次数 ak\texttt{a}k 的形式。例如,aaaabccdddd\texttt{aaaabccdddd} 被压缩成 a4b1c2d4\texttt{a4b1c2d4}

输入格式

第一行,一个只含小写字母和数字的压缩后的字符串 ss'

第二行,一个非负整数 cc

输出格式

一个小写字母,表示答案。

r2d2
8
r
a4b1c2d10
100
d

提示

样例解释

  • 样例 11 解释:r2d2\texttt{r2d2} 压缩前是 rrdd\texttt{rrdd}

重复无数多次即为 rrddrrddrrdd\texttt{rrddrrdd\textcolor{red}{r}rdd}\cdots

  • 样例 22 解释:a4b1c2d10\texttt{a4b1c2d10} 压缩前是 aaaabccdddddddddd\texttt{aaaabccdddddddddd}

子任务

对于 100%100\% 的数据,保证:

  • 2s1052\le |s'|\le 10^5
  • ss' 中出现的整数的范围是 [1,1012][1,10^{12}]
  • 0c10120\le c\le 10^{12}

  • Subtask 0(0 points)\text{Subtask 0(0 points}):样例。
  • Subtask 1(6 points)\text{Subtask 1(6 points})
    • 0c2×1030\le c\le 2\times 10^3
    • ss' 中出现的整数的范围是 [1,9][1,9]
    • 压缩前,ss 的长度不超过 20002000
  • Subtask 2(3 points)\text{Subtask 2(3 points})
    • 0c1060\le c\le 10^6
    • 压缩前,ss 的长度不超过 10610^6
  • Subtask 3(3 points)\text{Subtask 3(3 points})
    • 压缩前,ss 的长度不超过 10610^6
  • Subtask 4(3 points)\text{Subtask 4(3 points}):无特殊限制。