定理
多面体欧拉定理的证明
定理内容 对于任何一个凸多面体，记它有 \(v\) 个顶点，\(f\) 个面和 \(e\) 条棱，那么满足以下关系： $$f+v-e=2$$ 定理证明 基本思路 用两种不同的方法计算并用 \(f,v,e\) 表示出这个凸面体所有面上的内角和，再列出等式化简得到最终结果。（角度上标均省略） 方法一：直 ......
Dilworth定理 转载
Dilworth定理 Dilworth定理，一言以蔽之，偏序集能划分成的最少的全序集个数等于最大反链的元素个数。——————litble 狄尔沃斯定理(Dilworth’s theorem)亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于 ......
莱斯定理
每次看完一遍证明就只能理解十几秒然后又不理解了 按照自己的理解方式尝试写下来一遍 Rice's Theorem: 对于非平凡的语言性质$P$, $P$是不可判定的。 注：$P$也可以理解为一个语言的集合，或者说字符串的集合的集合 证明： 反证，如果$P$是可判定的，那么存在图灵机$M_P$来判定，这 ......
【算法设计与分析】(二)分治_更新中①：二分搜索、计数、选择、最近点对、凸包、多项式乘法、矩阵乘法、主定理&递归树、傅里叶。苏大计科院研一期末复习笔记
写在前面 首先，本人很菜。 其次，本文只也许够应付考试，个人使用。而且其实就是ppt内容只是我自己喜欢这样整理。虽然全力理解内容且认真书写但也可能存在错误，如有发现麻烦指正，谢谢🌹 最后，因为不知道考试怎么考，本人的复习方式是照着目录讲一遍自己的理解+写伪代码（如果来的及会再做一个综合纯享版），再 ......
主定理
定义 主定理（Master Theorem）通常是指在算法分析领域中的一个定理，特别是用于分析递归算法的时间复杂度。 时间复杂度相关定义 在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。其原理在于，将计算机的每种基本运算（如加减乘除）所需的时 ......
裴蜀定理
定义 设 \(a,b\) 是不全为 \(0\) 的整数 1.对任意整数 \(x,y\)，满足 \(\gcd(a,b)|ax+by\) 2.存在整数 \(x,y\) 使得 \(ax+by=\gcd(a,b)\) 证明 第一条 理解一下即可，比较好理解 第二条 若任何一个等于 \(0\)，则 \(\gc ......
霍尔定理
一个二分图有完美匹配，当且仅当，对于左部点的任意一个子集（设其大小为 \(x\)），右部点有和此点集直接连边的点的集合大小（设为 \(y\)），满足 \(x\le y\) 的关系 证明： 必要性显然，充分性可以使用数学归纳法 某道相关题目 ......
欧拉定理
欧拉定理 设\(a,m\)是正整数，且\(\gcd(a,m)=1\),那么\(a^{\varphi (m)}\equiv 1(\bmod m)\) 欧拉定理的推论： 设\(a,m\)是正整数，且\(\gcd(a,m)=1\),那么\(a^b\equiv a^{b\bmod \varphi (m)}( ......
欧拉定理 & 扩展欧拉定理 笔记
欧拉函数 欧拉函数定义为：\(\varphi(n)\) 表示 \(1 \sim n\) 中所有与 \(n\) 互质的数的个数。 关于欧拉函数有下面的性质和用途： 欧拉函数是积性函数。可以通过这个性质求出他的公式。 \(f(p) = p - 1\)。很显然，比质数 \(p\) 小的所有数都与他互质。 ......
扩展中国剩余定理（Excrt）笔记
扩展中国剩余定理（excrt） 本来应该先学中国剩余定理的。但是有了扩展中国剩余定理，朴素的 CRT 就没用了。 扩展中国剩余定理用来求解如下形式的同余方程组： \[\begin{cases} x \equiv a_1\ ({\rm mod}\ b_1) \\ x\equiv a_2\ ({\rm ......
Burnside 引理 与 Pólya 定理 学习笔记
为了防止明天就把好不容易听完的东西都还给 rabbit_lb 了，还是记一点吧。 1. 群论基础 1.1 群(group) 的定义 给定集合 \(G\) 和 \(G\)上的二元运算 \(\cdot\)，满足下列条件称之为群： 封闭性：若 \(a,b\in G\)，则 \(a\cdot b\in G\ ......
金牌导航-Burnside引理与Polya定理
Burnside引理与Polya定理 例题A题解 Polya模板。 Polya定理给出，如果设有限集 \(D\) 的置换群为 \(G\)，\(C\) 是由全体用 \(m\) 种颜色为 \(D\) 中颜色染色的方案构成的集合，每个置换 \(\sigma\) 的循环总数是 \(c(\sigma)\)，那 ......
P5091 【模版】扩展欧拉定理
求 \(a^b \bmod m, b\le 10^{200000}\)。 首先引入三种可以通过取模缩小幂指数的方法。 费马小定理：当 \(a,p\in \mathbb{Z},\space p\) 为质数且 \(p\nmid a\) 时，\(a^{p-1}\equiv 1(\bmod\space p) ......
主定理
参考文章：时间复杂度及主定理详解，托比欧：主定理 Master Theorem。 简介 在算法分析中，主定理（英语：master theorem）提供了用渐近符号表示许多由分治法得到的递推关系式的方法。 在初赛题目中，主定理可以用来计算形如 \(T(n)=a\times T(n/b) + O(n^{ ......
Newton-Leibniz公式、可积的充分必要条件、积分中值定理、微积分基本定理
    为不全为 \(0\) 的整数，\(ax+by=c\) 有整数解当且仅当 \(\text{gcd}(a,b)|c\)。定理容易推广到多个整数的情况。 此题中，由裴蜀定理的推广得，\(\text{gcd}(A_1,A_2\cdots A_n)|S\)，取 \(S\) 为最小公约 ......
闭区间上连续函数的基本定理
 \)表示不超过\(n\)的与\(n\)互质的正整数个数 特别的：\(\varphi (1)=1\) 给出一些例子： \(\varphi (2)=1,\varphi (3)=2,\varphi (4)=2,\varphi (5)=4\) 不难得出若\( ......
实数完备性基本定理
  ，计算 \(n\) 个元素的集合 \(\{1,2,\cdots,n\}\)，所有非空子集和的乘积取模 \(998 \, 244 \, 353\) 后的结果。 Input 一个正整数 \(n\) \((1\le n\le200)\)，代 ......
鞅与停时定理 例题记录
鞅与停时定理，一个很厉害的东西，感觉像是一种势能分析。 关于它具体是什么，笔者的数学水平还不足以讲述，所以在这里推广一下：概率论科技：鞅与停时定理 - littleZ_meow 的小窝。 下面的写法可能很不专业，请自行避雷。 给出一种很 OI 的解释：你需要设计一个函数 \(f(x)\)，有次能够得 ......
Matrix-Tree 定理
行列式求值 交换矩阵 \(A\) 两行，\(\det(A') = -\det(A)\) 。 将矩阵 \(A\) 的第 \(i\) 行乘 \(k\) 后，\(\det(A') = k\times\det(A)\)。 将矩阵 \(A\) 的第 \(i\) 行乘 \(k\) 后加到第 \(j\) 行上，\ ......
亲情的欧拉定理
欧拉定理指出 产量分配净尽定理，指在完全竞争的条件下， 假设长期中规模收益不变，则全部产品正好足够分配给各个要素。 白话版 如果总量不变的前提下 产出的产品正好足够分配给各个要素 增加了要素 每个要素就会减少 生产硬件不更新，本质不变化，分配不是无限的 亲情 人的的爱总量是有限的 小时候我们分配了给 ......
微分中值定理
微分中值定理 一、罗尔定理 内容 如果函数 \(f(x)\) 满足： 在 \([a,b]\) 上连续； 在 \((a,b)\) 内可导； 在区间端点处的函数值相等，即 \(f(a)=f(b)\)。 那么在 \((a,b)\) 内至少有一点 \(\xi(a<\xi<b)\) 使得函数 \(f(x)\) ......
微分中值定理
微分中值定理 罗尔定理 观察下图 设曲线 \(AB\) 是函数 \(y=f(x) (x \in [a,b])\) 的图形. 图中两端点的纵坐标相等，即 \(f(a) = f(b)\) 可以发现在曲弧线的最高点 \(C\) 处或最低点 \(D\) 处，曲线有水平的切线. 记 \(C\) 点的横坐标为 ......
【数论】欧拉函数 欧拉定理&费马小定理 12.8学习小结
开篇碎碎念： 在咕咕咕的接近两周时间内看了些数论，但是由于对于latex的不熟悉所以就没有整理笔记出来，总的来说就是学了下exgcd、crt。然后回老家玩了一阵子所以咕咕咕。今天啃一啃欧拉函数&欧拉定理之类的，然后就可以组合数学启动啦！ヽ(✿ﾟ▽ﾟ)ノ 欧拉函数 参考博文：Plozia的欧拉函数 定 ......