矩阵快速幂

OI
矩阵快速幂.md

前置技能

矩阵乘法

复杂度为$O(n^3)$,有复杂度稍低的分治写法,不过意义不大(毕竟你的矩阵这么小)

$A,B$是两个矩阵,其中$A$是$m\times n$的矩阵,$B$是$x\times y$的矩阵

当且仅当$n=x$时$A\cdot B$有意义。

快速幂

OI

普通的快速幂

问题[COGS 1433]圣庙里的汉诺塔

计算$a^b\mod m$,其中$0\leq a,b\leq10^{16}$。

我们可以写出如下的暴力求幂程序,复杂度$O(n)$:

1
2
3
4
5
6
7
8
typedef long long ll;
ll pow_mod(ll a,ll b,ll m)
{
ll ans=1;
while(b--)
ans=(ans*a)%m;
return ans;
}

不过注意到对于任意正整数k,我们都可以拆成至多$log k$个二进制下的1,所以我们可以计算出$a^{2^0},a^{2^1},a^{2^2},\cdots$(可以递推出来),然后再用$\log b$次乘法将其合并起来,复杂度为$O(\log n)$,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
ll fast_pow_mod(ll a,ll b,ll m)
{
ll ans=1;
while(b)
{
if(b&1)
ans*=a;
a*=a;
b>>=1;
}
return ans;
}

由快速幂魔改的快速乘

问题:[COGS 2037]Asm.def大点兵

由于$a\times b$可能溢出,因此不能直接乘起来再取膜,考虑到一个事实:
$$
a^b=
\begin{cases}
1 & b=0 \
\underbrace { a \times \cdots \times a }_b & b \ge 1
\end{cases}
$$
$$
a\times b=
\begin{cases}
0&b=0\
\underbrace{a+\cdots+a}_b&b\not=0
\end{cases}
$$
所以我们把上面的代码稍微改一改就好了: