Part 1. 引子
求有多少 1 ∼ n 1\sim n 1∼n的排列，满足：
- 进行
k
k
k轮原神排序后变为升序
具体的，一轮原神排序的定义为：
- 指针 i i i按 [ 1 , n ) [1,n) [1,n)的顺序正序遍历，如果 a i > a i + 1 a_i>a_{i+1} ai>ai+1，则交换 a i a_i ai和 a i + 1 a_{i+1} ai+1
- 指针
i
i
i按
(
1
,
n
]
(1,n]
(1,n]的顺序逆序遍历，如果
a
i
−
1
>
a
i
a_{i-1}>a_i
ai−1>ai，则交换
a
i
−
1
a_{i-1}
ai−1和
a
i
a_{i}
ai
1 ≤ n ≤ 1 0 18 , 0 ≤ k ≤ 1 0 5 1\le n\le 10^{18},0\le k\le 10^5 1≤n≤1018,0≤k≤105
Part 2
首先转化成对 01 01 01序列排序，发现每次操作等价于将最左边的 1 1 1和最右边的 0 0 0进行交换，然后转二分图匹配模型，设 f i , j f_{i,j} fi,j表示决策了前 i i i个左部点和右部点，左部点和右部点分别有 j j j个点未匹配的方案数。转移如下：
f i , j = { f i − 1 , j − 1 + ( 2 j + 1 ) f i − 1 , j + ( j + 1 ) 2 f i − 1 , j + 1 0 ≤ j ≤ k 0 j > k f_{i,j}=\begin{cases}f_{i-1,j-1}+(2j+1)f_{i-1,j}+(j+1)^2f_{i-1,j+1}&0\le j\le k\\0&j>k\end{cases} fi,j={fi−1,j−1+(2j+1)fi−1,j+(j+1)2fi−1,j+100≤j≤kj>k
可能你看不懂上面的递推式是怎么来的，这是本题的难点之一，但是我们先略过这一部分。考虑写出转移矩阵 A A A，那么答案就是 A n v A^nv Anv。注意到转移可以写成 k + 1 k+1 k+1阶矩阵，有结论：对于向量 v v v的任意一维，存在相同的 k + 1 k+1 k+1阶递推式。
证明：考虑找出矩阵 A A A的特征多项式 ∑ c i A i = 0 \sum c_iA^i=0 ∑ciAi=0，记 j j j处的答案向量为 f j f_j fj，则：
∑ c i A i f j = 0 \sum c_iA^if_j=0 ∑ciAifj=0
考虑向量的任意一维（比如说这道题要求的是 f n , 0 f_{n,0} fn,0），则：
∑ c i f j + i , 0 = 0 \sum c_if_{j+i,0}=0 ∑cifj+i,0=0
这样我们自然而然的得到了线性递推式。
现在考虑求特征多项式，即 det ( λ I − A ) \text{det}(\lambda I-A) det(λI−A)。注意到其只在主对角线和副对角线上有值，记 d n d_n dn表示对应 n n n阶行列式的答案，展开得到：
d n = ( x − 2 n − 1 ) d n − 1 + ( n − 1 ) 2 d n − 2 d_n=(x-2n-1)d_{n-1}+(n-1)^2d_{n-2} dn=(x−2n−1)dn−1+(n−1)2dn−2
注意这不是常系数齐次线性递推，而是若干矩阵的乘积：
M i = [ 0 ( i − 1 ) 2 1 x − 2 i − 1 ] M_i=\begin{bmatrix}0&(i-1)^2\\1&x-2i-1\end{bmatrix} Mi=[01(i−1)2x−2i−1]
现在要求 ∏ i = 1 k + 1 M i \prod_{i=1}^{k+1}M_i ∏i=1k+1Mi，可以直接分治求，复杂度 O ( k log 2 k ) O(k\log^2 k) O(klog2k)。
最后用著名的 Bostan-Mori 算法求解常系数齐次线性递推的第 n n n项即可。
如果你不会这个
简单练习题：[ABC300Ex] Fibonacci: Revisited
总复杂度 O ( k log k log n + k log 2 k ) O(k\log k\log n+k\log^2 k) O(klogklogn+klog2k)。
代码：
//很抱歉这份代码咕掉了。只能期待Hagasei-Chan给出的std了。
Part 3
还有一个题的递推式大概是这样的：
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 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} fi,0=fi−a,0+fi−a,2+fi−a,3fi,1=fi−b,1+fi−b,2+fi−b,3fi,2=fi−c,0+fi−c,1+fi−c,2fi,3=fi−d,0+fi−d,1+fi−d,3
现在要求 f n , 0 + f n , 1 + f n , 2 + f n , 3 f_{n,0}+f_{n,1}+f_{n,2}+f_{n,3} fn,0+fn,1+fn,2+fn,3。
可以考虑写成生成函数的形式然后硬解方程，这样解出来应该是封闭形式，可以直接上 Bostan-Mori 。
但是其实这玩意也可以写成矩阵转移的形式，然后暴力展开行列式。因为有值的地方很少所以也是可行的。
Part 4
总结：我是属于连递推式都看不出来的那种bot题谁做啊？bot题谁做啊？bot题谁做啊？bot题谁做啊？
猜你喜欢
网友评论
- 搜索
- 最新文章
- 热门文章