Loading...

关于数列变换的一些技巧

check评论:0 条 remove_red_eye浏览量:122 change_historyTags:编程学习笔记
作者 : Decoration date_range日期 : 2019-07-02

给定一个长度为$n$的序列,经过一些变换,输出最后的序列

思路$1$,打表

思路$2$,矩阵快速幂

将每一种变换都写成矩阵形式,之后用矩阵快速幂

举个例子

翻转数列 1 2 3 4

用矩阵乘法的形式写出来,就是$\begin{matrix} 1\ 2\ 3 \ 4 \end{matrix}$ $\times$ $\begin{matrix}\ 0\ 0\ 0\ 1\ \\0\ 0\ 1\ 0\\0\ 1\ 0\ 0\\1\ 0\ 0\ 0\end{matrix}$ $=$ $\begin{matrix} 4\ 3\ 2\ 1 \end{matrix}$

然后将各种规则矩阵乘在一起,快速幂即可

如果需要进行区间加入,考虑给矩阵增加一行以表示系数,然后如果增加$1$就乘$1$即可

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名