《算法竞赛进阶指南》笔记

2021/11/15 22:12:21

本文主要是介绍《算法竞赛进阶指南》笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 0x30 数学知识
    • 0x33 同余
      • 概念与定理
        • 例题The Luckiest Number
      • 扩展欧几里得算法$(exgcd)$
        • 定理及概念
      • 线性同余方程
      • 高次同余方程
    • 0x34 矩阵乘法
    • 0x35 高斯消元与线性空间
      • 高斯消元
      • 线性空间
    • 0x36 组合计数
      • 基本概念
      • 组合数的求法
      • 二项式定理
      • 多重集的排列数与组合数
      • Lucas 定理
      • Catalan 数列

0x30 数学知识

0x33 同余

概念与定理

定义: 如果\(a\%m = b\%m\),则 \(a\) 与 \(b\) 模 \(m\) 同余, \(m\) 为正整数,记作 \(a\equiv b\pmod m\)

同余类: 对于 \(\forall a \subset [0, m-1]\) ,集合 \({a+km}(k\subset Z)\) 的所有模 \(m\) 同余,余数都是 \(a\)。该集合就是一个模 \(m\) 的同余类,记为 \(\bar{a}\)

完全剩余系: 模 \(m\) 的同余类一共有 \(m\) 个,分别为 \(\bar{1},\bar{2},\dots,\overline{m-1}\) ,是一个完全剩余系。

简化剩余系: \(1~m\) 中与 \(m\) 互质的数代表的同余类共有\(\varphi(m)\) 个,它们构成 \(m\) 的简化剩余系,例如,模 \(10\) 的简化剩余系为 \({\bar{1}, \bar{3}, \bar{7}, \bar{9}}\) 。( \(\varphi(n)\) 大小为小于 \(n\) 的所有与 \(n\) 互质的正整数个数)

若 \(a, b(1 ≤ a,b ≤ m)\) 与 \(m\) 互质, 则 \(a*b\) 与 \(m\) 也互质,也能属于 \(m\) 的简化剩余系。

费马小定理: 若 \(p\) 是质数,则对于任意整数 \(a\),有 \(a^p\equiv a\pmod p\)。

欧拉定理: 若正整数 \(a,n\) 互质,则 \(a^{\varphi(n)}\equiv 1\pmod n\),其中 \(\varphi(n)\) 为欧拉函数。

(证明略)

其中,若 \(p\) 是一个质数,则 \(\varphi(p) = p - 1\)。

欧拉定理的推论: 若正整数 \(a,n\) 互质,则对于任意正整数 \(b\),有 \(a^b\equiv a^{b\mod \varphi(n)}\pmod n\)。

对答案取模 \(p\) 的应用技巧:

  • 面对 \(a+b,a-b,a*b\) 这种算式,先对 \(a,b\) 分别对 \(p\) 取模。
  • 面对乘法算式, 根据欧拉定理的推论,先将底数对 \(p\) 取模$、质数对 \(\varphi(p)\) 取模,再计算乘方。
  • 特别地,当 \(a,n\) 不一定互质且 \(b>\varphi(n)\) 时,有 \(a^b\equiv a^{b\mod \varphi(n) + \varphi(n)}\pmod n\),即意味着,即便底数 \(a\) 与 模数 \(n\) 不互质,也能把指数的规模给缩小。 (指数循环节证明)

例题The Luckiest Number

此题由欧拉函数引出一个推理:

  • 满足 \(a^x\equiv1\pmod n\) 的最小的 \(x\), \(x_0\) 是 \(\varphi(n)\) 的约数。

此题启发点:

  • \(x\) 个 \(8\) 连起来的数可以写作 \(8(10^x-1)/9\),题意是求最小的 \(x\),满足 \(L\mid 8(10^x -1)\)。设 \(d=gcd(L,8)\),然后推导运用引理。

扩展欧几里得算法\((exgcd)\)

定理及概念

\(Bezout\) 定理:对于任意整数 \(a,b\) ,存在一对整数 \(x,y\), 满足 \(ax+by=gcd(a,b)\)。

乘法逆元:

线性同余方程

高次同余方程

0x34 矩阵乘法

0x35 高斯消元与线性空间

高斯消元

线性空间

0x36 组合计数

基本概念

加法原理: 完成一件事有 \(n\) 类方法,其中第 \(i\) 类方法包括 \(a_i\) 种不同的方法,且方法之间相互独立,则完成这件事共有 \(a_1+a_2+\ldots+a_n\) 种不同方法。

乘法原理: 完成一件事要 \(n\) 个步骤,其中第 \(i\) 个步骤有 \(a_i\) 种不同的方法,方法、步骤之间相互独立,则完成这件事共有 \(a_1*a_2*\cdots*a_n\) 种不同方法。

排列数: 从 \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列,产生的不同排列的数量为:

\[A_n^m(也可记作P_n^m)=\frac{n!}{(n-m)!}=n*(n-1)*\cdots*(n-m+1) \]

组合数: 从 \(n\) 个不同的元素中取出 \(m\) 个组成一个集合(无顺序),产生的不同集合数量为:

\[C_n^m=\frac{n!}{m!(n-m)!}=\frac{n*(n-1)*\cdots*(n-m+1)}{m*(m-1)*\cdots*2*1} \]

组合数性质:

  1. \(C_n^m=C_n^{n-m}\)
  2. \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1}\)
  3. \(C_n^0+C_n^1+C_n^2+\cdots+C_n^m=2^n\)

组合数的求法

二项式定理

多重集的排列数与组合数

Lucas 定理

Catalan 数列



这篇关于《算法竞赛进阶指南》笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程