原神启动（递推，矩阵）

Part 1. 引子

求有多少$1～n$的排列，满足：

• 进行$k$轮原神排序后变为升序

具体的，一轮原神排序的定义为：

• 指针$i$按$[1,n)$的顺序正序遍历，如果$a_i>a_{i+1}$，则交换$a_i$和$a_{i+1}$
• 指针$i$按$(1,n]$的顺序逆序遍历，如果$a_{i?1}>a_i$，则交换$a_{i?1}$和$a_i$

$1\le n\le 10^{18},0\le k\le 10^5$

Part 2

首先转化成对$01$序列排序，发现每次操作等价于将最左边的$1$和最右边的$0$进行交换，然后转二分图匹配模型，设$f_{i,j}$表示决策了前$i$个左部点和右部点，左部点和右部点分别有$j$个点未匹配的方案数。转移如下：

$$f_{i,j}=\{\begin{array}{ll}{f}_{i?1,j?1}+(2j+1)f_{i?1,j}+(j+1{)}^2{f}_{i?1,j+1}& 0\le j\le k\\ 0& j>k\end{array}$$

可能你看不懂上面的递推式是怎么来的，这是本题的难点之一，但是我们先略过这一部分。

考虑写出转移矩阵$A$，那么答案就是$A^{n}v$。注意到转移可以写成$k+1$阶矩阵，有结论：对于向量$v$的任意一维，存在相同的$k+1$阶递推式。

证明：考虑找出矩阵$A$的特征多项式$\sum c_i{A}^i=0$，记$j$处的答案向量为$f_j$，则：

$$\sum c_i{A}^i{f}_j=0$$

考虑向量的任意一维（比如说这道题要求的是$f_{n,0}$），则：

$$\sum c_i{f}_{j+i,0}=0$$

这样我们自然而然的得到了线性递推式。

现在考虑求特征多项式，即$\text{det}(\lambda I?A)$。注意到其只在主对角线和副对角线上有值，记$d_n$表示对应$n$阶行列式的答案，展开得到：

$$d_n=(x?2n?1)d_{n?1}+(n?1{)}^2{d}_{n?2}$$

注意这不是常系数齐次线性递推，而是若干矩阵的乘积：

$$M_i=\left[\begin{array}{cc}0& (i?1{)}^2\\ 1& x?2i?1\end{array}\right]$$

现在要求${\prod }_{i=1}^{k+1}{M}_i$，可以直接分治求，复杂度$O(k{\log }^{2}k)$。

最后用著名的 Bostan-Mori 算法求解常系数齐次线性递推的第$n$项即可。

如果你不会这个

简单练习题：[ABC300Ex] Fibonacci: Revisited

总复杂度$O(k\log k\log n+k{\log }^{2}k)$。

代码：

//很抱歉这份代码咕掉了。只能期待Hagasei-Chan给出的std了。

Part 3

还有一个题的递推式大概是这样的：

$$\begin{gathered} f_{i,0}=f_{i?a,0}+f_{i?a,2}+f_{i?a,3} \\ {f}_{i,1}=f_{i?b,1}+f_{i?b,2}+f_{i?b,3} \\ {f}_{i,2}=f_{i?c,0}+f_{i?c,1}+f_{i?c,2} \\ {f}_{i,3}=f_{i?d,0}+f_{i?d,1}+f_{i?d,3} \end{gathered}$$

现在要求$f_{n,0}+f_{n,1}+f_{n,2}+f_{n,3}$。

可以考虑写成生成函数的形式然后硬解方程，这样解出来应该是封闭形式，可以直接上 Bostan-Mori 。

但是其实这玩意也可以写成矩阵转移的形式，然后暴力展开行列式。因为有值的地方很少所以也是可行的。

Part 4

总结：我是属于连递推式都看不出来的那种

bot题谁做啊？bot题谁做啊？bot题谁做啊？bot题谁做啊？