前情提要
题面
给定模 \(2\) 意义下的三元组 \((x, y, z)\)，初始时 \(x = y = z = 0\)，每次操作等概率随机选取 \(x, y, z\) 其中一个 \(+1\)，求 \(2n\) 次操作后回到 \((0, 0, 0)\) 的概率。
思路
一开始可以先考虑一下，只有当操作在 \(x, y, z\) 上的次数均为偶数时才可，不过这样列出一个二元求和还是挺难的（
不妨转化一下，感觉这很像一个游走问题。
如图：
画同样颜色的概率相同。
不过这么分析有点麻烦，优化一下。
这个偶数步的限制有点烦，所以将一步化为走两步。
这样只有红色和蓝色能够到达了。
变为：
于是设 \(A_i, B_i\) 表示走 \(i\) 步到达 \(A, B\) 的概率。
得到：
\[A_i = \frac{1}{3}A_{i - 1} + \frac{2}{9}B_{i - 1}
\]
\[B_i = \frac{2}{3}A_{i - 1} + \frac{7}{9}B_{i - 1}
\]
得到这个式子，感觉不太好处理，怎么办？
别忘了一个极度重要的东西，\(A_i + B_i = 1\)，所有概率之和为 \(1\)。
于是就能消除掉 \(B_{i - 1}\) 了。
\[A_i = \frac{1}{9}A_{i - 1} + \frac{2}{9}
\]
这个就比较典了，直接展开就好。
得到：
\[A_i = \frac{2}{9}\sum_{j = 0}^{i - 1}(\frac{1}{9})^j + (\frac{1}{9})^i
\]
化简得到：
\[A_n = \frac{1}{4} + \frac{3}{4}\times(\frac{1}{9})^n
\]