定理

Kirchhoff 矩阵树定理的无向图情况 定义 无向图无自环。 设 \(G\) 为包含 \(n\) 个点，\(m\) 条边的无向图。 设 \(\deg(i)\) 表示顶点 \(i\) 的度数，\(E(i,j)\) 表示顶点 \(i\) 与 \(j\) 连边的条数。 记边 \(i\) 的起点为 \( ......

前置知识 有向图游戏概念。 单个有向图游戏中 \(\textrm{SG}\) 函数的求值（\(\textrm{mex}\) 运算）。 以上内容请自行查阅，这里不会多说。 前言 本文受启发于 OI Wiki，采用相同的数学归纳法进行证明，但对计算的原理进行了补充，也补足了一些细节。 网上许多 \(\t ......

我们现在要讨论能否用机器完成证明的问题。在这里，我们所说的机器就是指图灵机。但为了讨论的方便，我们在这里使用一个图灵机的等价模型寄存器机。它有\(m\)个用来存放符号串的内存，能够写入某个内存末尾加字符、减字符、跳转、打印和停机五种指令。一个寄存器机程序（简称程序）就是有限条寄存器机上的指令（且最后 ......

算数基本定理 定理 对于整数 \(a > 1\)，必有 \(a=p_1^{a_1}p_2^{a_2}\dots p_s^{a_s}\)，其中 \(p_j(1\leq j\leq s)\) 是两两不相等的质数，\(a_j(1\leq j\leq s)\) 表示对应质数的幂次。在不计次序的意义下，该分解 ......

本文参考知乎大神明月清风的圆锥曲线一类定点问题研究。 首先给出 Frégier 定理： 定理（Frégier定理）：设有圆锥曲线 \(E\) 及其上一定点 \(P\)，设 \(E\) 上两点 \(B,C\) 满足 \(A\) 在以 \(BC\) 为直径的圆上，则直线 \(BC\) 过定点 \(D\) ......

前言 以前写过一篇关于二次方程根的分布问题的博文，感觉思路混乱，也不想再修改，故重新开一篇博文探讨这个问题，初次尝试用零点存在定理来分析二次方程根的分布，自编题目，有待商榷，希望多提宝贵意见。 典例分析 为了降低思维的难度，我们首先看这个比较特殊的例子， 已知函数 \(f(x)=-x^2+2x+1- ......

题目链接 ：H-数学_2023 中国大学生程序设计竞赛（CCPC）新疆赛区 (nowcoder.com) 题意 ： 有数学知识可知： 本题如果根据贪心， 每个先用最大的数来凑，会出错，比如12 == 9 + 1 + 1 + 1， 但是答案是12 == 4 + 4 + 4，就会出错 题解思路dp[], ......

我们讨论何为“证明”。一个证明过程实际上是在给定条件的基础上，反复运用始终可以使用的基本规则，最后推演出想要的结论的过程。这个过程可以形式化地描述，称为Sequent Calculus。由formula集合\(\Phi\)能“证明”出formula \(\varphi\)，记为\(\Phi \vda ......

裴蜀定理 在数论中，裴蜀等式（英语：Bézout's identity）或裴蜀定理（Bézout's lemma）（或称贝祖等式）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 \(a\) 和 \(b\) 和 \(m\)，关于未知数 \(x\) 和 ......

对于一个信号，我们想对其进行采样转化成数字信号，显然，当我们采样频率越改，我们所能保留的信息越多，但是当高采样频率对我们的采样设备要求也高，我们希望找到采样频率和模拟信号频率之间的一些关系 有模拟信号$x_(t)\(，我们对其进行理想采样，即采样信号\)\hat{(t) =}x(t)\sum\lim ......

如果ABQ三点共线，则OQ=a*OA+b*OB，且a+b=1，其中O表示不在直线AB上的任意点，当然如果原点不在直线AB上，用原点也是成立的。 参考 向量三点共线定理 (baidu.com) 向量的三点共线定理及应用_百度知道 (baidu.com) ......

题目描述 给定一张 \(n\) 个结点 \(m\) 条边的带权图（可能为无向图，可能为有向图）。 定义其一个生成树 \(T\) 的权值为 \(T\) 中所有边权的乘积。 求其所有不同生成树的权值之和，对 \(10^9+7\) 取模。 注意： 本题中，有向图的生成树指的是 以 \(1\) 为根的外向树 ......

中国剩余定理及其扩展定理 学习笔记 中国剩余定理，又叫孙子定理，最早出现在我国古代著作《孙子算经》中，OI 中常称其为 CRT(China Remainder Theorem)。 问题 CRT 用于求解线性同余方程组问题，且模数互质： \[(a_1, a_2, ..., a_n) = 1\\\beg ......

一、离散时间鞅 定义离散时间鞅为一个时间离散的随机过程 \(X_0, X_1, \ldots\)，使得 \(\forall n \in \mathbb{N}\)，均满足： \(E(|X_n|) < \infty\)。 \(E(X_{n + 1} - X_n \mid X_0, X_1, \ldots ......

1. 奈氏准则 奈氏，定义极限传输速率，为 2W LB(V) -- LB() 以二为底的对数， V是电平数。例如，0001 电平数为 4; 【例1】 在无噪声的情况下，若某通信链路的带宽为3kHz,采用4个相位，每个相位具有四种振幅的QAM调制技术，则该通信链路的最大数据传输率是多少？ 信号有 4× ......

卢卡斯定理/Lucas 定理 引入 求 \(C_{n+m}^n \mod p\)。 \(n,m,p \leq 10^5\)。 如果直接用阶乘求，可能在阶乘过程中出现了 \(p\)，而最后的结果没有出现 \(p\)，导致错误。 有两种解决方法： 1.求组合数时提前把 \(p\) 的质因子除掉。 2.L ......

射影定理 条件：\(AB\perp BC,BD\perp AC\)。 结论： \(AB^2=AD\times AC\) \(BC^2=CD\times CA\) \(BD^2=DA\times DC\) 线束定理 条件：\(DE//BC\)。 结论：\(\dfrac{DF}{FE}=\dfrac{B ......

见到的一个小推广，但感觉挺有用，记录一下。 对于一个如下形式的网络最大流： 其左部边 \(a\) 能流满，当前仅当对于任意左部点点集 \(S\)，\(\sum\limits_{x\in S}a_x\le \sum\limits_{y\in T}b_y\)，其中 \(T\) 为 \(S\) 相邻的右部 ......

Hall 定理： Hall定理： 设一个二分图，V1<=V2。 则V1能完美匹配的条件是，对于所有点集S属于V1，V1能到达V2的点集S2，满足S2>=S1 ex_Hall定理： 设一个二分图，V1<=V2 则，这个图的最大匹配ans=min(|V1-S1|+|S2|)=|V1|-max(|S1|- ......

建立流体模型 对于一段流体 质量具有连续性，其密度为 \(ρ\) 流速为 \(v\) 流体横截面积为 \(S\) 微元研究 微元作用时间：\(Δt\) 微元作用长度：\(vΔt\) 则对应的质量为： \[Δm=ρSvΔt \]随后建立方程，应用动量定理研究即可。 ......

裴蜀定理 定义 裴蜀定理，又称贝祖定理（Bézout's lemma）。是一个关于最大公约数的定理。 其内容是： 设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\), 使得 \(ax+by=\gcd(a,b)\). 证明 若任何一个等于 \(0\), 则 \(\gcd(a,b)=a\) ......

卢卡斯定理 引入 卢卡斯定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解，但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到卢卡斯定理。 定义 卢卡斯定理内容如下：对于质数 \(p\)，有 \[\binom{n}{m} ......

威尔逊定理 定义 威尔逊定理：对于素数 \(p\) 有 \((p-1)!\equiv -1\pmod p\)。 证明 我们知道在模奇素数 \(p\) 意义下，\(1,2,\dots ,p-1\) 都存在逆元且唯一，那么只需要将一个数与其逆元配对发现其乘积均为（同余意义下）\(1\)，但前提是这个数的 ......

费马小定理 定义 若 \(p\) 是质数，且 \(\gcd(a, p) = 1\)，则有 \(a^{p - 1} \equiv 1 \pmod{p}\)。 另一个形式：对于任意整数 \(a\)，有 \(a^p \equiv a \pmod{p}\)。 证明 设一个质数为 \(p\)，我们取一个不为 ......

欧拉函数 互质：对于 \(\forall a, b \in \mathbb{N}\)， 若 \(a, b\) 的最大公因数为 \(1\) ， 则称 \(a, b\) 互质。 欧拉函数:即 $ \varphi (N)$, 表示从 \(1\) 到 \(N\) 中与 \(N\) 互质的数的个数。 在算术基 ......

欧拉函数与欧拉定理 欧拉函数 定义 欧拉函数，即 \(\varphi(n)\)，表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。 比如说 \(\varphi(1) = 1\)。 当 n 是质数的时候，显然有 \(\varphi(n) = n - 1\)。 性质 欧拉函数是积性函数。 积 ......

引言 网络上有许多Hall定理的证明，但是对于Hall定理的几个推广的介绍却少之又少，因此本文来简单介绍一下 注：为了使这篇文章看起来简单易懂，本文将不会使用图论语言，会图论的朋友们可以自行翻译为图论语言。 背景： 在遥远的地方有一个神奇国家，这个国家有n个男生和m个女生（n m）。每个男生都喜欢着 ......

引言 什么是韦达定理？它描述了二次方程的两根关系： \[\cases{x_1x_2=\cfrac{c}{a}\\x_1+x_2=-\cfrac{b}{a}} \]本文将简洁证明韦达定理。 证明 求根公式 我们知道求根公式： \[x=\cfrac{-b\pm\sqrt{b^2-4ac}}{2a} \] ......

\(n!\) 中含素数 \(p\) 的幂次为 \(\displaystyle\sum_{i=1}\lfloor\frac{n}{p^{i}}\rfloor\) Kummer 定理：\({n+m\choose n}\) 中含素数 \(p\) 的幂次等于 \(p\) 进制下 \(n+m\) 的进位次数 ......

我们来补习一下统计学习框架的正式模型。 输入 一个学习者可以访问以下内容 作用域集合 (Domain set)：一个任意的集合 \(\mathcal X\)，学习者的目标是对其上面的元素进行标记。 标签集合 (Label set)：所有可能的标签 \(\mathcal Y\)。许多时候被限制为 \( ......