Problem 803

Pseudorandom sequence

Rand48 is a pseudorandom number generator used by some programming languages. It generates a sequence from any given integer $0 \leq a_{0} < 2^{48}$ using the rule $a_{n} = (25214903917 \cdot a_{n - 1} + 11) mod 2^{48}$ .

Let $b_{n} = ⌊ a_{n} / 2^{16} ⌋ mod 52$ . The sequence $b_{0}, b_{1}, \dots$ is translated to an infinite string $c = c_{0} c_{1} \dots$ via the rule:

$0 \to$ a, $1 \to$ b, $\dots$ , $25 \to$ z, $26 \to$ A, $27 \to$ B, $\dots$ , $51 \to$ Z.

For example, if we choose $a_{0} = 123456$ , then the string $c$ starts with: “bQYicNGCY $\dots$ ”.

Moreover, starting from index $100$ , we encounter the substring “RxqLBfWzv” for the first time.

Alternatively, if $c$ starts with “EULERcats $\dots$ ”, then $a_{0}$ must be $78580612777175$ .

Now suppose that the string $c$ starts with “PuzzleOne $\dots$ ”.

Find the starting index of the first occurrence of the substring “LuckyText” in $c$ .

伪随机序列

许多编程语言都使用Rand48这种伪随机数生成器。对于任意给定整数 $0 \leq a_{0} < 2^{48}$ ，它会按照规则 $a_{n} = (25214903917 \cdot a_{n - 1} + 11) mod 2^{48}$ 生成一组伪随机序列。

记 $b_{n} = ⌊ a_{n} / 2^{16} ⌋ mod 52$ 。序列 $b_{0}, b_{1}, \dots$ 会进一步按照以下规则翻译为无限长字符串 $c = c_{0} c_{1} \dots$ ：

$0 \to$ a， $1 \to$ b， $\dots$ ， $25 \to$ z， $26 \to$ A， $27 \to$ B， $\dots$ ， $51 \to$ Z。

例如，如果我们选择 $a_{0} = 123456$ ，那么字符串 $c$ 的开头部分为：”bQYicNGCY $\dots$ ”。

进一步地，在字符串下标为 $100$ 的位置，我们第一次得到子串”RxqLBfWzv”。

另一方面，如果我们希望字符串 $c$ 的开头部分为”EULERcats $\dots$ ”，那么 $a_{0}$ 必须选定为 $78580612777175$ 。

现在假设字符串 $c$ 的开头部分为”PuzzleOne $\dots$ ”。

求我们第一次在字符串 $c$ 中得到子串”LuckyText”的起始位置下标。