适用场景

主要适用于快速计算一个 monoid 对象的多次 concat 运算后的结果。核心点在于减少 concat 的调用次数。时间复杂度大致上为logN。

monoid 定义伴随着：

tsx
...
declare function makeUnit(): T;
declare function concat(lhs: T, rhs: T): T;

// monoid需要满足,其中a，b，c是T类型的任意值
concat(concat(a, b), c) === concat(a, concat(b, c)); // 交换律
concat(makeUnit(), a) === concat(a, makeUnit()) && concat(makeUnit(), a) === a; // 拥有单位元

代码框架

tsx
...
const quickPow = <T>(value: T, count: number) => {
  let n = count;

  let ans = makeUnit(); // value.makeUnit() 一般希望makeUnit是静态方法
  let currValue = value;

  while (n) {
    if (n & 1) {
      // n为奇数
      ans = concat(ans, currValue);
    }
    currValue = concat(currValue, currValue);
    n = n >> 1; // n = n /2;
  }

  return ans;
};

常见题型

计算某个数的指数与某指定数的余数。

背景知识补充

求余有如下规律： (a*b)%c =((a%c)*b)%c = ((a%c)*(b%c))%c,即任意两数乘积的求余，等价于任意因子的求余结果的乘积再取余的结果。

故修改concat函数为

tsx
...
const concat = ((lhs, rhs) = ((lhs % c) * (rhs * c)) % c);

快速计算数列An

面对a_{n} = a * a_{n-1} + b * a_{n-2} + c*a_{n-3},可以整理的如下矩阵：

latex
...
\begin{bmatrix}
a_{n} \\
a_{n-1} \\
a_{n-2}
\end{bmatrix}
=
\begin{bmatrix}
a & b & c \\
1 & 0 & 0 \\
0 & 1 & 0 
\end{bmatrix}
\begin{bmatrix}
a_{n-1} \\
a_{n-2} \\
a_{n-3}
\end{bmatrix}
LaTex公式知多少

故问题转变为特定矩阵的n-3次方的计算。