← 完整题目索引

PROJECT EULER · #0980

四元数群 I

The Quaternion Group I

仅题目 · 待解原题 ↗

从一个空字符串开始,我们想要构建一个包含字母"x"、"y"、"z"的字符串。在每个步骤中,都会执行以下操作之一:

  • 在字符串中的任意位置插入两个连续的相同字母"xx"、"yy"或"zz";
  • 根据以下规则将字符串中的一个字母替换为两个连续字母:"x" → "yz", "y" → "zx", "z" → "xy";
  • 交换字符串中两个连续的不同字母,例如"xy" → "yx"、"zx" → "xz" 等

如果在偶数步后可以从空字符串生成字符串,则该字符串称为中性。

我们定义一个序列 (an)n≥0:a0=88888888 和 an=(8888⋅an−1)mod888888883 对于 n>0。

令 bn=anmod3。对于每个 i≥0,长度为 50 的字符串 c(i) 通过以下规则转换有限序列 b50i,b50i+1,…,b50i+49 来定义:0→ "x", 1→ "y", 2→ "z"。

令 F(N) 为 0≤i,j<N 的有序对 (i,j) 的数量,这样连接的字符串 c(i)c(j) 是中性的。
例如,F(10)=13 和 F(100)=1224。

求 F(106)。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。