矩阵快速幂
「SDOI2008」递归数列-矩阵快速幂
· ✏️ 672 words · ☕ 2 mins read

一个由自然数组成的数列按下式定义:

对于 $i \leq k$ :$a_i = b_i$

对于 $i > k$ : $a_i = c_1a _ {i-1} + c_2a _ {i-2} + … + c_ka _ {i-k}$

其中 $b_j$ 和 $c_j$ ( $1 \leq j \leq k$)是给定的自然数。写一个程序,给定自然数 $m \leq n$, 计算 $a_m + a _ {m+1} + a _ {m+2} + … + a_n$, 并输出它除以给定自然数 $p$ 的余数的值。

对于 100% 的测试数据:

$1 \leq k \leq 15,1 \leq m \leq n \leq 10^{18},0 \le b_1, b_2,… b_k, c_1, c_2,…, c_k \leq 10^9,1 \leq p \leq 10^8$


「TJOI2015」棋盘-状压dp+矩阵快速幂
· ✏️ 902 words · ☕ 2 mins read

有一个 $n$ 行 $m$ 列的棋盘,棋盘上可以放很多特殊的棋子,每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3 \times p$ 的矩阵给出了棋子攻击范围的模板,棋子被默认在模板中的第 [二] 行,第 [$k+1$] 列,模板中棋子能攻击到的位置标记为 1,不能攻击到的位置是 0 $(1 \leq p \leq m, 0 \leq k < p)$。输入数据保证模板中的第 [二] 行第 [$k+1$] 列是 1

打开门的密码是这样的:在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意什么棋子都不摆也算作一种可行方案。请求出方案对 $2^{32}$ 取余的结果即可。


「NOI2012」随机数生成器-矩阵快速幂
· ✏️ 286 words · ☕ 1 mins read

给定正整数 $n,m,a,c,X[0],g$ ,求按照 $X[n+1] = (a X[n] + c) \bmod m$ 生成出的第 $n$ 项 $X[n] \bmod g$ 的值。

数据范围: $n,m,a,c,X[0] \leq 10^{18}$


「HNOI2008」GT考试-KMP+dp+矩阵快速幂
· ✏️ 547 words · ☕ 2 mins read

阿申准备报名参加 $GT$ 考试,准考证号为 $n$ 位数 $X_1X_2\cdots X_n(0\le X_i\le 9)$,他不希望准考证号上出现不吉利的数字。

他的不吉利数字 $A_1A_2\cdots A_m(0\le A_i\le 9)$ 有 $m$ 位,不出现是指 $X_1X_2\cdots X_n$ 中没有恰好一段等于 $A_1A_2\cdots A_m$,$A_1$​ 和 $X_1$ 可以为 $0$。

阿申想知道不出现不吉利数字的号码有多少种,输出模 $K$ 取余的结果。


「SDOI2009」HH去散步-矩阵快速幂+dp
· ✏️ 731 words · ☕ 2 mins read

HH 是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为 HH 是个喜欢变化的人,所以他每天走过的路径都不完全一样,他想知道他究竟有多少种散步的方法。

现在给你学校的地图(假设每条路的长度都是一样的都是 $1$ ),问长度为 $t$ ,从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合上述条件的路径。