朴素做法
明显可以进行状压DP，用 \(f_{i, j}\) 表示在第 \(i\) 行时下一行状态为 \(j\) 的方案数。
但是这样复杂度是 \(\Omicron(n2^{2m})\) 的，即便预处理优化也只能达到 \(\Omicron(nm2^m)\) ，因此需要对算法进行优化。
优化思路+方法
发现每次从 \(f_{i, j}\) 转移向 \(f_{i + 1, j}\) 时，转移方式与 \(i\) 其实并无关系。所以并不需要求出中间的值，只需要求出连续转移 \(i\) 次最后的值。
然后仔细观察转移步骤，发现对于每个可转移关系 \((x, y)\) ，将 \(f_{i, x}\) 叠加向 \(f_{i + 1, y}\)。这是一种线性变换。
于是考虑用矩阵实现这种线性变换。
也就是将原始情况 \(f_0 = [1, 0, 0, \dots, 0]\) 与变化矩阵进行 \(n\) 次矩阵乘法，得到 \(f_n\)。
然后就找到了可以优化的点。
众所周知，矩阵可以相乘，其意义为先后进行两次变换所等价的变换，而且这种乘法具有结合律。