RenaMoe's Blog

念念不忘，必有回响

0%

总结 OI中一些数学定理

发表于 更新于 分类于 ， Valine：

这里放一些数学公式定理，防止健忘。

好吧现在已经是远古博客了，慎用。

Matrix Tree 定理

定义一个图 \(G\) 的 \(\rm Kirchhoff\) 矩阵 \(C=\text{度数矩阵}-\text{邻接矩阵}\) \[ C_{i,j}= \begin{cases} degree_i& (i=j)\\ -1& (i\not=j\ and\ (i,j)\in G(E))\\ 0& (i\not=j\ and\ (i,j)\notin G(E)) \end{cases} \] 将矩阵 \(C\) 去掉任意一行和一列，该矩阵的行列式即图 \(G\) 的 生成树个数

概率相关

\(P(A)\) ： \(A\) 事件发生的概率

\(E(X)\)：随机变量 \(X\) 的期望值，\(E(X)=\sum P(X=i)\times i\)

\(P(A|B)\)：\(A\) 在 \(B\) 发生的条件下发生的概率，\(P(A|B)=\frac{P(AB)}{P(B)}\)

全概率公式：\(P(B)=\sum_{i=1}^n{P(A_i)P(B|A_i)}\)

贝叶斯公式：\(P(A_i|B)=\frac{P(B|A_i)P(A_i)}{\sum_{j=1}^n{P(B|A_j)P(A_j)} }\) （不会，不知道有没有用）

期望的性质：

\(E(X+Y)=E(X)+E(Y)\)

\(E(aX+b)=aE(X)+b\)

\(E(XY)=E(X)+E(Y)\) （ \(x,y\) 相互独立）

辛普森积分

\[ \frac{b-a}{6}[f(a)+4f(\frac{a+b}{2})+f(b)] \]

自适应辛普森，分成左右分别套辛普森法则，不断拟合：

1
2
3
4
5
6
7
8
9
10
11
inline double simpson(double l, double r) {
    double mid = (l + r) / 2;
    return (f(l) + 4 * f(mid) + f(r)) * (r - l) / 6;
}
double solve(double l, double r, double last, double eps) {
    double mid = (l + r) / 2;
    double ln = simpson(l, mid), rn = simpson(mid, r);
    if (abs(ln + rn - last) <= eps)
    return ln + rn + (ln + rn - last);
    return solve(l, mid, ln, eps/2) + solve(mid, r, rn, eps/2);
}

## 模性质

模意义下加、减、乘随便做，除要转换成逆元

\(a\equiv b\pmod p\nRightarrow \frac{a}{2}\equiv \frac{b}{2}\pmod p\)

裴蜀定理

对于不定方程：\(ax+by=c\)

有（整数）解的充要条件为 \(\gcd⁡(a,b) | c\)

即一定存在 \(x,y\) 满足 \(ax+by=\gcd(a,b)\)

推论：\(a,b\) 互素等价于 \(ax+by=1\) 有解

欧几里得算法

gcd

\[ \gcd(a,b)=\gcd(a-b,b) \]

1
2
3
4
5
6
7
8
9
10
11
// 递归
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
// 非递归
int gcd(int a, int b) {
    int t;
    while (b)
        t = a, a = b, b = t % a;
    return a;
}

exgcd

\[ ax+by=\gcd(a,b)\\ bx'+(a\%b)y'=\gcd(b,a\%b) \]

将 \(a\ mod\ b\) 替换为 \(a-\lfloor\frac{a}{b}\rfloor b\) ，得 \[ \begin{align} bx'+(a\%b)y'&=bx'+(a-\lfloor\frac{a}{b}\rfloor b)y'\\ &=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y') \end{align} \] 则 \(x,y\) 和 \(x',y'\) 的关系为 \[ x=y',y=x'-\lfloor\frac{a}{b}\rfloor y' \] 当 \(b=0\) 时，\(x'=1\) ，\(y\) 可以为任何值

1
2
3
4
5
6
7
8
void exgcd(int a, int b, int &x, int &y, int &gcd) {
    if (!b) {
    	x = 1, y = 0, gcd = a;
        return;
    }
    exgcd(b, a%b, y, x, gcd);
    y -= a / b * x;
}

求出的 x,y 为某一组解，x 通解为 \(x+k\times\frac{b}{\gcd(a,b)}\)。

整数唯一分解定理

对于任意整数 \(N\ (N\ge2)\) \[ \large N=\prod_{i=1}^k{p_i^{r_i}}\quad (p_i\text{为质数},r_i\ge0) \]

\(N\) 的正约数集合：\(\large\{\prod_{i=1}^k{p_i^{b_i}}\}\ (0\le b_i\le r_i)\)

\(N\) 的正约数个数：\(\large\prod_{i=1}^k{(r_i+1)}\)

\(N\) 的正约数和：\(\large\prod_{i=1}^k(\sum_{j=0}^{r_i}p_i^j)\)

威尔逊定理

\(p\) 是质数的充要条件为: \[ (p-1)!\equiv -1\pmod p \]

费马小定理

\(p\) 为质数，且 \(\gcd(a,p)=1\) ，则： \[ a^{p-1}\equiv 1\pmod p \] 故 \(a\) 在模 \(p\) 下的乘法逆元为 \(a^{p-2}\)

线性预处理逆元

设 \(p=i*k+r(0\le r\le i)\)

\[ i*k+r\equiv 0\pmod p \]

两边乘 \(i^{-1}r^{-1}\)

\[ k\times r^{-1}+i^{-1}\equiv 0 \pmod p \\ i^{-1}\equiv -k\times r^{-1}\pmod p \]

其中 \(r=p\%i,k=\lfloor\frac{p}{i}\rfloor\)

1
2
3
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i)
    inv[i] = (p - p / i) * inv[p%i] % p;

还有一种方法：

设 \(s_i=\prod_{j=1}^{i}a_i,invs_i=s_i^{-1}\)

\(O(\log_2(mod))\) 预处理 \(invs_n\) ，则 \(invs_i=invs_{i+1}\times a_{i+1}\)

1
2
3
4
5
6
7
8
s[0] = 1;
for (int i = 1; i <= n; ++i)
    s[i] = s[i-1] * a[i] % p;
invs[n] = power(s[n], p-2);
for (int i = n - 1; i; --i)
    invs[i] = invs[i+1] * a[i+1] % p;
for (int i = 1; i <= n; ++i)
    inv[i] = invs[i] * s[i-1] % p;

欧拉函数

\[ \varphi(n)=\sum_{i=1}^n[\gcd(n, i)=1] \]

若 \(p\) 为素数，则 \(\varphi(p)=p-1\)

若 \(\gcd(a,b)=1\)，则 \(\varphi(ab)=\varphi(a)\varphi(b)\)

基于素因数分解求 \(\varphi(n)\) ，复杂度 \(O(\sqrt{n})\) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
int euler_phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            res = res / i * (i - 1); 
            while (n % i == 0)
                n /= i;
        }
    }
    if (n != 1) 
        res = res / n * (n - 1);
    return res;
}

欧拉定理

\(a,p\) 为互质的正整数 \[ a^{\varphi(p)}\equiv 1\pmod p \]

扩展欧拉定理

若 \(a,p\) 不一定互质，且 \(x\ge \varphi(p)\) \[ a^x\equiv a^{x\%\varphi(p)+\varphi(p)}\pmod p \]

中国剩余定理

crt

对于一元线性同余方程组： \[ \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ ……\\ x\equiv a_n\pmod{m_n} \end{cases} \] 其中 \(m_i\) 两两互质

该方程组的通解为： \[ M=\prod_{i=1}^nm_i\\ M_i=\frac{M}{m_i}\\ t_i=M_i^{-1}\pmod{m_i}\\ x\equiv \sum_{i=1}^n{a_it_iM_i\pmod M} \]

excrt

见总结

拉格朗日插值

对于一个给定 n 个点 \((x_i,y_i)\) 的多项式，可以 \(O(n^2)\) 算出该多项式在 \(x_k\) 的取值 \[ f(x_k)=\sum_{i=1}^n{y_i\prod_{i\not=j}\frac{x_k-x_j}{x_i-x_j}} \] 如果已知取值 \(x_1\) 到 \(x_n\) 是连续的话，可以预处理前缀积优化到 \(O(n\log n)\)（逆元再线性处理就是 \(O(n)\) ）

莫比乌斯函数

\[ \mu(n)= \begin{cases} 1& (n=1)\\ (-1)^k& (n\text{无平方数因数},n=\prod_{i=1}^k{p_i})\\ 0& (n\text{有大于1的平方数因数}) \end{cases} \]

\[ \sum_{d\mid n}\mu(d)= \begin{cases} 1& (n=1)\\ 0& (n=0) \end{cases}\\ \sum_{d\mid n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n} \]

一些积性函数

  • \(\varphi(n)\)：欧拉函数
  • \(\mu(n)\)：莫比乌斯函数
  • \(\gcd(n,k)\)：（\(k\) 固定时）最小公因数
  • \(d(n)\)：\(n\) 的约数个数
  • \(\sigma(n)\)：\(n\) 的约数和
  • \(1(n)=1\)
  • \(id(n)=n\)
  • \(e(n)=\begin{cases}1&(n=1) \\ 0 &(n\not=1) \end{cases}\)

狄利克雷卷积

\[ h=f\times g\\ h(n)=\sum_{i\mid n}{f(i)*g(\frac{n}{i})} \]

两个数论函数的狄利克雷卷积结果仍是一个数论函数

两个积性函数的狄利克雷卷积仍是一个积性函数

狄利克雷卷积满足交换律、结合律

Lucas定理

\[ \binom{n}{m}\equiv\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\bmod p}{m\bmod p}\pmod p \]

待补充……