P5678 [GZOI2017]河神 题解-世界视讯
2023-03-24 21:15:03
哔哩哔哩
这道题显然是一道利用矩阵乘法优化递推的题目，毕竟给了一个数列的递推公式，但是：
(资料图片)
——这是什么公式啊，没有正常的运算也就算了，还多了个 ，什么人啊~~~
那么我们得考虑推广矩阵乘法的运算法则，使得矩阵乘法仍然满足结合律但是却适应这道题目的特殊情况。或者说，我们需要找到加法、乘法运算和与、或运算的共通之处，从而进行推广。（这很像数学家干的事情啊，不是嘛）
我们可以考虑把加法变成或运算，乘法变成与运算。这里简要证明一下乘法变成与运算的合理性（也就是依然具有结合律）：
的第 位为 当且仅当至少存在一对 使得 第 位全部为 。
的第 位为 当且仅当至少存在一对 使得 第 位全部为 。
——引自 q779 奆佬对本题的题解（洛谷P5678 [GZOI2017]河神 题解 | Q779的博客）
接下来我们就可以找到初始矩阵，即：
然后又有转移矩阵：
其中 取 。
接着矩阵快速幂优化递推即可。
Code:
