這道題顯然是一道利用矩陣乘法優(yōu)化遞推的題目，畢竟給了一個數(shù)列的遞推公式，但是：

——這是什么公式啊，沒有正常的運算也就算了，還多了個?，什么人啊~~~

那么我們得考慮推廣矩陣乘法的運算法則，使得矩陣乘法仍然滿足結(jié)合律但是卻適應這道題目的特殊情況?；蛘哒f，我們需要找到加法、乘法運算和與、或運算的共通之處，從而進行推廣。（這很像數(shù)學家干的事情啊，不是嘛）

我們可以考慮把加法變成或運算，乘法變成與運算。這里簡要證明一下乘法變成與運算的合理性（也就是依然具有結(jié)合律）：

?的第??位為??當且僅當至少存在一對??使得??第??位全部為?。

?的第??位為??當且僅當至少存在一對??使得??第??位全部為?。

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

接下來我們就可以找到初始矩陣，即：

然后又有轉(zhuǎn)移矩陣：

其中??取?。

接著矩陣快速冪優(yōu)化遞推即可。

Code: