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

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

¶二分法

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

¶解决问题

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

¶小数

规定精度 eps = 1e-6 or 1e-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 的数列，求各个元素从本身开始能构成的最长有趣元素的长度。

二分答案的写法模板

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$
快速求出 $a^{2 $，$ a}4 $，$ a^{8 $，$ a}{16} \dots $将$ b $做二进制拆分$ a^b = a^{b_1} \cdot a^{b_2} \cdot \dots \cdot a^{b_k}$
$O(\log b)$

¶代码实现

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}$