Cloud_Player's Notes
0%

二分三分快速幂矩阵快速幂

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

b站视频链接：北京理工大学ACM冬季培训课程
课程刷题地址 2020BIT冬训-二分三分快速幂矩阵快速幂 Password: bitacm2020
本篇博文为看视频学习时的记录与自己的一些总结

二分三分快速幂矩阵快速幂

二分法

  • 思想简单，主要讲实现
  • 写法多种多样
  • lower_bound upper_bound(begin, end, val)

解决问题

  • 具有单调性 / 连续性的问题二分查找
  • 最大最小问题 / 最小最大问题二分答案
  • 判断前缀的合法性二分前缀长度
  • 分数规划问题二分答案

小数

  • 规定精度 eps = 1e-6 or 1e-8
1
2
3
4
5
6
7
8
double left, right, mid;
while (right - left > eps)
{
    mid = (right + left) / 2;
    if (judge(mid)) left = mid;
    else right = mid;
}
return mid;

二分答案

  • 适用情况：求最值，可能答案区间有限且单调，检验答案合理性复杂度低

一个例子

如果一个数列中 2*K 的元素中前 K 个元素和与后 K 个元素和都不大于 S。那么我们说这些元素是有趣的。给定 S，给你一个长度为 N 的数列，求各个元素从本身开始能构成的最长有趣元素的长度。

二分答案的写法模板

1
2
3
4
5
6
7
8
9
10
11
while (l <= r)
{
    int mid = (l + r) >> 1;
    if (judge(mid))
    {
        ans = mid;
        l = mid + 1;
    }
    else r = mid - 1;
}
return ans;

【例】aggressive cows

  • 有 n 个牛栏，分别位于 X1，X2，…Xn。选 m 个放进牛，使得相邻牛之间的最小距离值最大。
    其中，m <= n <= 1e5，0 <= Xi <= 1e9

  • 二分答案的标志：最小值最大 / 最大值最小

【例】Multiplication Table

  • 有 n * m 乘法表，将 n * m 个数从小到大依次排列，第 K 个数是多少？
    其中，K <= n, m <= 5e5

  • 二分的过程很简单，重点是判断答案的合理性

三分法

  • 二分：单调区间

  • 三分：凸性函数

以求最大值为例

  • 对比 f(lmid) 与 f(rmid)
  • 若 f(lmid) < f(rmid) 那么区间变为 lmid ~ r
  • 否则变为 l ~ rmid

（图解）

快速幂

  • 求 $a^b \bmod p$

  • $a^{2i} = a^i \cdot a^i$
    快速求出 $a2$，$a4$，$a8$，$a{16} \dots$
    将 $b$ 做二进制拆分
    $a^b = a^{b_1} \cdot a^{b_2} \cdot \dots \cdot a^{b_k}$

  • $O(\log b)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
int quickpow(int a, int p, int mod)
{
    int ans = 1; a = a % mod;
    while (p)
    {
        if (p & 1) ans = (ans * a) % mod;
        p >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

矩阵快速幂

矩阵乘法

  • $c_{ij} = \sum a_{ik} \times b_{kj}$

  • 第一个矩阵是 $n \times m$，第二个矩阵是 $m \times p$

  • $O(nmp)$

矩阵快速幂

  • 将快速幂中的底数变为矩阵

  • 优势：线性递推式

【例】斐波那契数列

  • 求斐波那契数列的第 n 项，n <= 1e18
    $F_i = F_{i-1} + F_{i-2}$，$F_1, F_0 = 1$

$\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \times \begin{pmatrix} F_{i-1} \ F_{i-2} \end{pmatrix} = \begin{pmatrix} F_i \ F_{i-1} \end{pmatrix}$

$\begin{pmatrix} F_n \ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n-1} \times \begin{pmatrix} F_1 \ F_0 \end{pmatrix}$

$\begin{pmatrix} F_{i-2} & F_{i-1} \ a & b \end{pmatrix} \times \begin{pmatrix} 0 & 1 \ 1 & 1 \end{pmatrix} = \begin{pmatrix} F_{i-2} & F_{i-1} \ b & a + b \end{pmatrix}$

一些递推式

推广，根据状态逆推系数矩阵

$F_i = a * F_{i-1} + b * F_{i-2}$

$\begin{pmatrix} a & b \ 1 & 0 \end{pmatrix} \times \begin{pmatrix} F_{i-1} \ F_{i-2} \end{pmatrix} = \begin{pmatrix} F_i \ F_{i-1} \end{pmatrix}$

$\begin{pmatrix} F_n \ F_{n-1} \end{pmatrix} = \begin{pmatrix} a & b \ 1 & 0 \end{pmatrix}^{n-1} \times \begin{pmatrix} F_1 \ F_0 \end{pmatrix}$

$F_i = a * F_{i-1} + i$

$\begin{pmatrix} a & 1 & 1 \ 0 & 1 & 1 \ 0 & 0 & 1 \end{pmatrix} \times \begin{pmatrix} F_{i-1} \ i-1 \ 1 \end{pmatrix} = \begin{pmatrix} F_i \ i \ 1 \end{pmatrix}$