格雷码 (相邻两个数字的二进制异或为二的次幂)#

两个数的二进制只有一个位数相差1

i^(i>>1) 这个能求出i的格雷码

1 000011 2 000001 3 000111 4 000001 5 000011 6 000001 7 001111 8 000001 9 000011 10 000001 11 000111 12 000001 13 000011 14 000001 15 011111 16 000001

16以内的格雷码数，相邻的格雷码数^=1;

矩阵快速幂构造方法总结#

在使用矩阵快速幂解决递推问题时，关键在于 构造初始矩阵和转移矩阵。下面以例题 a_i = a_{i-3} + a_{i-1} 为例总结方法。

1️⃣ 构造初始矩阵（Basic Matrix）#

根据题意，已知前几个项：a_1 = a_2 = a_3 = 1。
初始矩阵存储这些已知值：

a₁	a₂	a₃
1	1	1

矩阵大小：
- 行：1（因为这是一个“行向量”）
- 列：保存多少个历史状态，就有多少列
  - 本例需要保存 a_i, a_{i-1}, a_{i-2} → 3 列
作用：基础矩阵保存初始状态，用于与转移矩阵相乘计算后续项。

2️⃣ 构造转移矩阵（Transfer Matrix）#

原递推式：a_i = a_{i-3} + a_{i-1}
为了计算 a_{i+1}，需要把矩阵状态向右移动，并引入新关系。
转移矩阵规则：
1. 第一列对应递推公式中参与计算的元素：
  - 本例：a_i 和 a_{i-2} 参与 → 第一列是 [1, 0, 1]
2. 其余列用于原封不动地转移历史状态：
  - 第二列对应 a_i → a_i
  - 第三列对应 a_{i-1} → a_{i-1}
最终转移矩阵示意：

	i	i-1	i-2
i+1	1	1	0
i	0	0	1
i-1	1	0	0

作用：
对基础矩阵乘以转移矩阵，可以将状态从 [a_i, a_{i-1}, a_{i-2}] 转移到 [a_{i+1}, a_i, a_{i-1}]。

3️⃣ 计算第 n 项#

我们要求 a_n，则只需：
1. 用初始矩阵（存储 a_1, a_2, a_3）乘上 转移矩阵的 n-1 次方
  [ \text{ans} = \text{basic matrix} \times (\text{transfer matrix})^{n-1} ]
2. 基础矩阵乘完后，第一格就是 a_n
优化：
- 转移矩阵幂用快速幂算法计算 → 时间复杂度 O(log n)
- 整个计算从暴力 O(n) 降为 O(log n)

4️⃣ 总结矩阵构造步骤#

确定基础矩阵：
- 行：1（或列向量）
- 列：保存递推所需历史状态数量
- 填入已知初始值
确定转移矩阵：
- 第一列：对应递推公式参与的元素
- 其余列：原封不动地保存历史状态
- 行列数与基础矩阵列数一致（方阵方便快速幂）
计算递推：
- 将基础矩阵乘以转移矩阵的 n-1 次幂
- 输出基础矩阵的第一格，即为答案