Problem 980
The Quaternion Group I
Starting from an empty string, we want to build a string with letters “x”, “y”, “z”. At each step, one of the following operations is performed:
- insert two consecutive identical letters “xx”, “yy” or “zz” anywhere into the string;
- replace one letter in the string with two consecutive letters, according to the rule: “x” $\to$ “yz”, “y” $\to$ “zx”, “z” $\to$ “xy”;
- exchange two consecutive different letters in the string, e.g. “xy” $\to$ “yx”, “zx” $\to$ “xz”, etc.
A string is called neutral if it is possible to produce the string from the empty string after an even number of steps.
We define a sequence $(a_n)_{n \ge 0}$: $a_0=88\ 888\ 888$ and $a_n=(8888\cdot a_{n-1})\bmod 888\ 888\ 883$ for $n \gt 0$.
Let $b_n = a_n \bmod 3$. For each $i \ge 0$, a string $c(i)$ of length $50$ is defined by translating the finite sequence $b_{50i},b_{50i+1},\dots,b_{50i+49}$ via the rule: $0 \to$ “x”, $1 \to$ “y”, $2 \to$ “z”.
Let $F(N)$ be the number of ordered pairs $(i, j)$ with $0 \le i, j \lt N$ such that the concatenated string $c(i)c(j)$ is neutral.
For example, $F(10) = 13$ and $F(100) = 1224$.
Find $F(10^6)$.
四元数群（一）
从空字符串开始，我们逐步构造一个仅由字母”x”、”y”、”z”构成的新字符串，其中每一步执行以下操作之一：
- 在字符串的任意位置插入两个连续的相同字母”xx”、”yy”或”zz”；
- 将字符串中的一个字母替换为两个连续字母，规则如下：”x” $\to$ “yz”，”y” $\to$ “zx”，”z” $\to$ “xy”；
- 交换字符串中两个相邻的不同字母，例如”xy” $\to$ “yx”，”zx” $\to$ “xz”，等等。
如果一个字符串可以从空字符串经过偶数步操作生成，则称之为中性字符串。
定义数列$(a_n)_{n \ge 0}$为：$a_0=88\ 888\ 888$；当$n \gt 0$时，$a_n=(8888\cdot a_{n-1})\bmod 888\ 888\ 883$。
记$b_n = a_n \bmod 3$。对每个$i \ge 0$，可以通过以下规则将有限数列$b_{50i},b_{50i+1},\dots,b_{50i+49}$转化为一个长度为$50$的字符串$c(i)$：$0 \to$ “x”，$1 \to$ “y”，$2 \to$ “z”。
记$F(N)$为满足$0 \le i, j \lt N$且拼接字符串$c(i)c(j)$是中性字符串的有序数对$(i, j)$数目。
例如，$F(10) = 13$，$F(100) = 1224$。
求$F(10^6)$。
译注：如果将题中的”x”、”y”、”z”对应四元数的三个基$i$、$k$、$j$（注意此处需要交换$j$和$k$），则每步操作都相当于在原数上乘以$-1$，偶数步操作后相当于未改变原数，因此可以称为中性。