2024基本算法一：位运算和快速幂、矩阵快速幂

位运算

1.二进制与十进制等其他进制

1.1二进制与十进制的联系与转换(举例)

二进制是计算机内部运算中采用的进制，在这样的进制系统下，只有 0,10,1 两个数字，计算机内部的所有运算（包括位运算）都是在二进制的基础上进行的。

但用二进制表示数字会让数字过长，因此为了方便表示的需要，通常会把二进制数转换为八进制或十六进制表示。

八进制

在八进制下，有 0,1,2,3,4,5,6,70,1,2,3,4,5,6,7 八个数字。

一般情况下，八进制数以 oxx（其中 o 为八进制的前缀，xx 代表八进制数）的形式来表示。

十六进制

在十六进制下，有 $0,1,2,3,4,5,6,7,8,9,A(10),B(11),C(12),D(13),E(14),F(15)$ 十六个数字。

十六进制与二进制相比，最大的优点就是表示的数字长度较短，一位十六进制数可以表示 4 位二进制数。

一般情况下，十六进制数以 0xdbf（其中 0x 为十六进制数的前缀）的形式来表示。

int a = 0b010101; // 二进制

    cout << a << endl;
    a = 012; // 八进制
    cout << a << endl;
    a = 0x12; // 十六进制
    cout << a << endl;
   printf("%d %o %x ", a, a, a);

进制间的相互转化

十进制转二进制/八进制/十六进制

这里以二进制为例来演示，其他进制的原理与其类似。

整数部分，把十进制数不断执行除 2 操作，直至商数为 0。读余数从下读到上，即是二进制的整数部分数字。小数部分，则用其乘 2，取其整数部分的结果，再用计算后的小数部分依此重复计算，算到小数部分全为 0 为止，之后从上到下，读所有计算后整数部分的数字，即为二进制的小数部分数字。

将33.25转化为二进制数
整数部分：
33/2=16	......1
16/2=8	......0
8/2=4	......0
4/2=2	......0
2/2=1	......0
1/2=0	......1
小数部分：
0.25*2=0.5	0
0.5*2=1		1

即 33.25=(100001.01)233.25 = (100001.01)_2

二进制/八进制/十六进制转十进制

还是以二进制为例。

二进制数转换为十进制数，只需将每个位的值，乘以 2i2^i 次即可，其中 ii 为当前位的位数，个位的位数为 0。

将11010.01(2)转换为十进制数
11010.01(2)=1*2^4+1*2^3+0*2^2+1*2^1+0*2^0+0*2^(-1)+1*2(-2)
        =26.25

即 (11010.01)2=(26.25)10(11010.01)_2 = (26.25)_{10}

二进制/八进制/十六进制间的相互转换

一个八进制位可以用 3 个二进制位来表示（因为 23=82^3 =8），一个十六进制位可以用 4 个二进制位来表示（24=162^4 = 16），反之同理。

二进制小数的转换

1.2 二进制的算术运算 (举例)

1.3二进制的逻辑运算：and &, or |, not | ~, xor ^ (举例)

它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

运算 运算符 数学符号表示 解释
与 & &\&、and⁡\operatorname{and} 只有两个对应位都为 11 时才为 11
或 | ∣\mid、or⁡\operatorname{or} 只要两个对应位中有一个 11 时就为 11
异或 ^ ⊕\oplus、xor⁡\operatorname{xor} 只有两个对应位不同时才为 11

注意区分逻辑与（对应的数学符号为 ∧\wedge）和按位与、逻辑或（∨\vee）和按位或的区别。

1.4 移位操作 ：>> << (注意与输入输出区别)

（优先级？） 需要注意的是，位运算符的优先级低于普通的算数运算符。

运算 - 优先级

2.bit 与 Byte

bit 表示二进制位，一般是 b 表示；Byte 表示字节，一般用 B 表示， 规定 1Byte = 8 bit。

  • 1024B=1KB1024 B = 1 KB

  • 1024KB=1MB1024 KB = 1 MB

  • 1024MB=1GB1024 MB = 1 GB

  • 1024GB=1TB1024 GB = 1 TB

    一般情况下， int 为32bit，占4 Byte。 可用以下代码查看：

    cout << sizeof (int) << endl;

变量在程序运行时是存在计算机的内存中的。内存可以看作是一个空间，但是这些空间是以字节为单位的，为了方便访问它是有地址编码的，我们可以想象成一个大厦，要去某一个房间得需要有房间号，我们可以用下面的语句来查看变量的开始存储地址(这个数是操作系统和编译器共同决定的，不用我们去操心)

int b = 1;
int * a = & b; // 这里的 a 就是 变量 b 的 指针

cout << sizeof(a) << endl; // 可以看到指针的大小
cout << a << endl << *a << endl; // 可以看出区别

结构体也可以有指针。

struct ST
{
  int a, b;
} st;
ST * ts = & st;

cout << sizeof(ST) << endl << sizeof(st) << endl;
cout << ts -> a << " " << ts -> b << endl;

会计算自己的程序占用多少的内存。(自己试验数组的大小)

3.补码

位运算 - 取反与补码(举例)

思考：0的反码与补码是多少？

4.lowbit运算

lowbit

5.xor 的常见用法

  1. 对 a∈[0,1]a \in [0, 1] 进行反转，可以直接 a ^ 1
  2. 对于非负数 n， 当 n 为偶数时， n ^ 1 = n + 1, 为奇数时， n ^ 1 = n - 1
  3. a ^ a = 0

快速幂

1.快速幂

p790 A^B

2.矩阵快速幂

1. 何为矩阵. 矩阵

引入

矩阵的引入来自于线性方程组。与向量类似，矩阵体现了一种对数据“打包处理”的思想。

例如，将线性方程组：

$$\begin{equation} \left\{ \begin{array}{c} 7x_1+8x_2+9x_3=13 \\ 4x_1+5x_2+6x_3=12 \\ x_1+2x_2+3x_3=11 \end{array} \right. \end{equation} $$

一般用圆括号或方括号表示矩阵。将上述系数抽出来，写成矩阵乘法的形式：

$$\begin{equation} \left( \begin{array}{ccc} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right) = \left( \begin{array}{c} 13 \\ 12 \\ 11 \end{array} \right) \end{equation} $$

简记为：

Ax=bAx=b

即未知数列向量 x，左乘一个矩阵 A，得到列向量 b。这个式子可以认为是线性代数的基本形式。

线性代数主要研究的运算模型是内积。内积是先相乘再相加，是行向量左乘列向量，得到一个数的过程。

矩阵乘法是内积的拓展。矩阵乘法等价于左边矩阵抽出一行，与右边矩阵抽出一列进行内积，得到结果矩阵的对应元素，口诀“左行右列”。

当研究对象是右边的列向量时，矩阵乘法相当于对列向量进行左乘。在左乘的观点下，矩阵就是对列向量的变换，将矩阵乘法中右边矩阵的每一个列向量进行变换，对应地得到结果矩阵中每一个列向量。

矩阵可以对一个列向量进行变换，也可以对一组列向量进行“打包”变换，甚至可以对整个空间——即全体列向量进行变换。当矩阵被视为对整个空间变换的时候，也就脱离了空间，成为了纯粹变换的存在。

定义

对于矩阵 AA，主对角线是指 Ai,iA_{i,i} 的元素。

一般用 II 来表示单位矩阵，就是主对角线上为 1，其余位置为 0。 如下面的三阶单位矩阵

$$\left[ \begin{matrix} 1 &0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{matrix} \right] $$

方阵

行数等于列数的矩阵称为方阵。方阵是一种特殊的矩阵。对于“n 阶矩阵”的习惯表述，实际上讲的是 n 阶方阵。

研究方程组、向量组、矩阵的秩的时候，使用一般的矩阵。研究特征值和特征向量、二次型的时候，使用方阵。

同型矩阵

两个矩阵，行数与列数对应相同，称为同型矩阵。

性质

矩阵的逆

AA 的逆矩阵 PP 是使得 A×P=IA \times P = I 的矩阵。

逆矩阵可以用 高斯消元 的方式来求。

运算

矩阵的线性运算

矩阵的线性运算分为加减法与数乘，它们均为逐个元素进行。只有同型矩阵之间可以对应相加减。

矩阵的转置

矩阵的转置，就是在矩阵的右上角写上转置“T”记号，表示将矩阵的行与列互换。

矩阵乘法

矩阵乘法

矩阵的乘法是向量内积的推广。

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设 AA 为 P×MP \times M 的矩阵，BB 为 M×QM \times Q 的矩阵，设矩阵 CC 为矩阵 AA 与 BB 的乘积，

其中矩阵 CC 中的第 ii 行第 jj 列元素可以表示为：

Ci,j=∑k=1MAi,kBk,jC_{i,j} = \sum_{k=1}^MA_{i,k}B_{k,j}

在矩阵乘法中，结果 CC 矩阵的第 ii 行第 jj 列的数，就是由矩阵 AA 第 ii 行 MM 个数与矩阵 BB 第 jj 列 MM 个数分别 相乘再相加 得到的。这里的 相乘再相加，就是向量的内积。乘积矩阵中第 ii 行第 jj 列的数恰好是乘数矩阵 AA 第 ii 个行向量与乘数矩阵 BB 第 jj 个列向量的内积，口诀为 左行右列。

线性代数研究的向量多为列向量，根据这样的对矩阵乘法的定义方法，经常研究对列向量左乘一个矩阵的左乘运算，同时也可以在这里看出“打包处理”的思想，同时处理很多个向量内积。

矩阵乘法满足结合律，不满足一般的交换律。

利用结合律，矩阵乘法可以利用 快速幂 的思想来优化。

在比赛中，由于线性递推式可以表示成矩阵乘法的形式，也通常用矩阵快速幂来求线性递推数列的某一项。

优化

首先对于比较小的矩阵，可以考虑直接手动展开循环以减小常数。

可以重新排列循环以提高空间局部性，这样的优化不会改变矩阵乘法的时间复杂度，但是会在得到常数级别的提升。

// 以下文的参考代码为例
inline mat operator*(const mat& T) const {
  mat res;
  for (int i = 0; i < sz; ++i)
    for (int j = 0; j < sz; ++j)
      for (int k = 0; k < sz; ++k) {
        res.a[i][j] += mul(a[i][k], T.a[k][j]);
        res.a[i][j] %= MOD;
      }
  return res;
}

// 不如
inline mat operator*(const mat& T) const {
  mat res;
  int r;
  for (int i = 0; i < sz; ++i)
    for (int k = 0; k < sz; ++k) {
      r = a[i][k];
      for (int j = 0; j < sz; ++j)
        res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
    }
  return res;
}

参考代码

一般来说，可以用一个二维数组来模拟矩阵。

struct mat {
  LL a[sz][sz];

  inline mat() { memset(a, 0, sizeof a); }

  inline mat operator-(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) {
        res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
      }
    return res;
  }

  inline mat operator+(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) {
        res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
      }
    return res;
  }

  inline mat operator*(const mat& T) const {
    mat res;
    int r;
    for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) {
        r = a[i][k];
        for (int j = 0; j < sz; ++j)
          res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
      }
    return res;
  }

  inline mat operator^(LL x) const {
    mat res, bas;
    for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
    while (x) {
      if (x & 1) res = res * bas;
      bas = bas * bas;
      x >>= 1;
    }
    return res;
  }
};

看待线性方程组的两种视角

看待矩阵 A，或者变换 A，有两种视角。

第一种观点：按行看，观察 A 的每一行。这样一来把 A 看作方程组。于是就有了消元法解方程的过程。

第二种观点：按列看，观察 A 的每一列。A 本身也是由列向量构成的。此时相当于把变换 A 本身看成了列向量组，而 x 是未知数系数，思考 A 当中的这组列向量能不能配上未知数，凑出列向量 b。

例如，文章开头的例子变为：

$$\begin{equation} \left( \begin{array}{c} 7 \\ 4 \\ 1 \end{array} \right) x_1+ \left( \begin{array}{c} 8 \\ 5 \\ 2 \end{array} \right) x_2+ \left( \begin{array}{c} 9 \\ 6 \\ 3 \end{array} \right) x_3 = \left( \begin{array}{c} 13 \\ 12 \\ 11 \end{array} \right) \end{equation} $$

解方程变为研究，是否可以通过调整三个系数 x，使得给定的三个基向量能够凑出结果的向量。

按列看比按行看更新颖。在按列看的视角下，可以研究线性无关与线性相关。

矩阵乘法的应用

矩阵加速递推

斐波那契数列（Fibonacci Sequence）大家应该都非常的熟悉了。在斐波那契数列当中，F1=F2=1F_1 = F_2 = 1，Fi=Fi−1+Fi−2(i≥3)F_i = F_{i - 1} + F_{i - 2}(i \geq 3)。

如果有一道题目让你求斐波那契数列第 nn 项的值，最简单的方法莫过于直接递推了。但是如果 nn 的范围达到了 101810^{18} 级别，递推就不行了，稳 TLE。考虑矩阵加速递推。

设 Fib(n)Fib(n) 表示一个 1×21 \times 2 的矩阵 $\left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right]$。我们希望根据 $Fib(n-1)=\left[ \begin{array}{ccc}F_{n-1} & F_{n-2} \end{array}\right]$ 推出 Fib(n)Fib(n)。

试推导一个矩阵 base\text{base}，使 Fib(n−1)×base=Fib(n)Fib(n-1) \times \text{base} = Fib(n)，即 $\left[\begin{array}{ccc}F_{n-1} & F_{n-2}\end{array}\right] \times \text{base} = \left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right]$。

怎么推呢？因为 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}，所以 base\text{base} 矩阵第一列应该是 [11]\left[\begin{array}{ccc} 1 \\ 1 \end{array}\right]，这样在进行矩阵乘法运算的时候才能令 Fn−1F_{n-1} 与 Fn−2F_{n-2} 相加，从而得出 FnF_n。同理，为了得出 Fn−1F_{n-1}，矩阵 base\text{base} 的第二列应该为 [10]\left[\begin{array}{ccc} 1 \\ 0 \end{array}\right]。

综上所述：$\text{base} = \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]$ 原式化为 $\left[\begin{array}{ccc}F_{n-1} & F_{n-2}\end{array}\right] \times \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right] = \left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right]$

转化为代码，应该怎么求呢？

定义初始矩阵 $\text{ans} = \left[\begin{array}{ccc}F_2 & F_1\end{array}\right] = \left[\begin{array}{ccc}1 & 1\end{array}\right], \text{base} = \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]$。那么，FnF_n 就等于 ans×basen−2\text{ans} \times \text{base}^{n-2} 这个矩阵的第一行第一列元素，也就是 $\left[\begin{array}{ccc}1 & 1\end{array}\right] \times \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]^{n-2}$ 的第一行第一列元素。

注意，矩阵乘法不满足交换律，所以一定不能写成 $\left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]^{n-2} \times \left[\begin{array}{ccc}1 & 1\end{array}\right]$ 的第一行第一列元素。另外，对于 n≤2n \leq 2 的情况，直接输出 11 即可，不需要执行矩阵快速幂。

为什么要乘上 base\text{base} 矩阵的 n−2n-2 次方而不是 nn 次方呢？因为 F1,F2F_1, F_2 是不需要进行矩阵乘法就能求的。也就是说，如果只进行一次乘法，就已经求出 F3F_3 了。如果还不是很理解为什么幂是 n−2n-2，建议手算一下。

下面是求斐波那契数列第 nn 项对 109+710^9+7 取模的示例代码（核心部分）。

const int mod = 1000000007;

struct Matrix {
  int a[3][3];

  Matrix() { memset(a, 0, sizeof a); }

  Matrix operator*(const Matrix &b) const {
    Matrix res;
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= 2; ++j)
        for (int k = 1; k <= 2; ++k)
          res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
    return res;
  }
} ans, base;

void init() {
  base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
  ans.a[1][1] = ans.a[1][2] = 1;
}

void qpow(int b) {
  while (b) {
    if (b & 1) ans = ans * base;
    base = base * base;
    b >>= 1;
  }
}

int main() {
  int n = read();
  if (n <= 2) return puts("1"), 0;
  init();
  qpow(n - 2);
  println(ans.a[1][1] % mod);
}

这是一个稍微复杂一些的例子。

$$\begin{gathered} f_{1} = f_{2} = 0\\ f_{n} = 7f_{n-1}+6f_{n-2}+5n+4\times 3^n \end{gathered} $$

我们发现，fnf_n 和 fn−1,fn−2,nf_{n-1}, f_{n-2}, n 有关，于是考虑构造一个矩阵描述状态。

但是发现如果矩阵仅有这三个元素 [fnfn−1n]\begin{bmatrix}f_n& f_{n-1}& n\end{bmatrix} 是难以构造出转移方程的，因为乘方运算和 +1+1 无法用矩阵描述。

于是考虑构造一个更大的矩阵。

$$\begin{bmatrix}f_n& f_{n-1}& n& 3^n & 1\end{bmatrix} $$

我们希望构造一个递推矩阵可以转移到

$$\begin{bmatrix} f_{n+1}& f_{n}& n+1& 3^{n+1} & 1 \end{bmatrix} $$

转移矩阵即为

$$\begin{bmatrix} 7 & 1 & 0 & 0 & 0\\ 6 & 0 & 0 & 0 & 0\\ 5 & 0 & 1 & 0 & 0\\ 12 & 0 & 0 & 3 & 0\\ 5 & 0 & 1 & 0 & 1 \end{bmatrix} $$

2. 怎么做快速幂

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 46ms
  4. Powered by Hydro v4.19.1 Community
}