P5678 [GZOI2017]河神 题解

这道题显然是一道利用矩阵乘法优化递推的题目，毕竟给了一个数列的递推公式，但是：

——这是什么公式啊，没有正常的运算也就算了，还多了个 ，什么人啊~~~

那么我们得考虑推广矩阵乘法的运算法则，使得矩阵乘法仍然满足结合律但是却适应这道题目的特殊情况。或者说，我们需要找到加法、乘法运算和与、或运算的共通之处，从而进行推广。（这很像数学家干的事情啊，不是嘛）

我们可以考虑把加法变成或运算，乘法变成与运算。这里简要证明一下乘法变成与运算的合理性（也就是依然具有结合律）：

 的第  位为  当且仅当至少存在一对  使得  第  位全部为 。

 的第  位为  当且仅当至少存在一对  使得  第  位全部为 。

——引自 q779 奆佬对本题的题解（洛谷P5678 [GZOI2017]河神 题解 | Q779的博客）

接下来我们就可以找到初始矩阵，即：

然后又有转移矩阵：

其中  取 。

接着矩阵快速幂优化递推即可。

Code: