【算法介绍】概率与期望及其计算
文章总览：群星岸落之夜如你所见，这篇文章的主题是概率与期望。众所周知，概率与期望早就占领了各大领域，比如说投篮的命中率可以表达一个选手的投篮水准，竞赛题目设置很多测试点来测试代码本质是一种抽样调查，等等等等。但是说概率与期望，在初中或者高中课本中都是占比非常大的部分（刚刚好我也打算顺手学了），所以这篇文章的前半部分注重于一些课本上的基础知识介绍与讲解，后面会浅浅的说一些信竞方面的概率期望。
下为本文大纲：
概率基本知识介绍及计算
全概率公式与贝叶斯公式
期望、方差与线性相关性
二项、超几何及正态分布
期望线性性以及简单运用
随机游走的问题概率模型
概念基础：穿过锁孔之风
样本空间与概率定义
古典概型与概率加乘
独立事件与条件概率
全概率与贝叶斯公式
概率定义：这是魔法哟关于概率的定义，你可能会说：“这玩意不是烂大街了嘛吗？还有人不会的？”正确的，概率的定义其实大家都知道是那个意思，可是实际上从稍微严谨的角度出发的概念以及一些性质可能并不广为人知，我们要学概率，就要从最基础概念开始：概率的基础——事件。
对于一个事件，可以是世间万物，比如说下面几个都可以是事件：
在一个既有青蛙又 ...
【算法介绍】斯特林数与卡特兰数
文章总览：落井当下石这篇文章讲的内容是斯特林数和卡特兰数，两个非常常用的计数类型数列，初赛常考（好吧我怎么感觉斯特林数我从来没有见到过）
本文内容限定如下：
第一类斯特林数推导及实现
第二类斯特林数推导及实现
斯特林数例题
卡特兰数推导及应用
卡特兰数例题
算法其一：得胜必追击
第一类斯特林数推导及实现
第二类斯特林数推导及实现
第一类斯特林数第一类斯特林数就是：将 $n$ 个不同物体排成 $k$ 个互不区分的非空圆排列的方案数。
可以简单的分来讨论，对于第一类斯特林数 $S1(n,k)$：
对于第 $n$ 个数新开了一个圆排列，方案数为 $S1(n-1,k-1)$。
对于第 $n$ 个数插入了以前某一个圆排列，方案数为 $(n-1)\times S1(n-1,k)$，因为在插入这个数以前，一共有 $n-1$ 个数，由于是圆排列，环上的空位数量还是 $n-1$ 个，所以乘起来。
边界条件也是非常的明显是 dp[0][0]=1 。
123456dp[0][0] = 1;for(int i = 1; i <= n; i++) { for(int j = 1; ...
【奇技淫巧】欧拉函数与欧拉定理
文章总览：坠临万界的星芒欧拉函数和欧拉定理也是非常基础的数论知识。欧拉函数做为积性函数，并且自身携带欧拉名称加持各种优良性质，被广泛的运用到各个数学推导方面；而欧拉定理更是必不可少，计算逆元是它最基本的运用，它也是凌驾于费马小定理的存在（费马小定理可以从欧拉定理中得出）；并且其拓展即拓展欧拉函数还可以在取模运算中缩小大指数范围，等等等等。接下来我们介绍无所不能的——欧拉函数与欧拉定理。
欧拉函数推导
欧拉函数性质
欧拉函数的计算
欧拉函数拓展
欧拉定理推导
拓展欧拉定理推导
概念基础：因缘假合的人身
欧拉函数推导
欧拉函数性质
欧拉函数基础推导关于欧拉函数，就从最基础的开始讲起。我们定义函数 $\varphi(n)$ 表示从 $1$ 到 $n$ 的数字中与 $n$ 互质的有多少个。这就是欧拉函数所表示的信息。那么关于欧拉函数我们能有什么已知的值吗？
非常显然的，对于一个质数 $p$，其欧拉函数值 $\varphi(p)=p-1$ 这是显然的，因为 $p$ 作为质数显然与 $1\sim p$ 之间的除了它本身以外任何数字互质。其次有一个容易让人纰漏的点，那就是 $\varphi(1 ...
【算法介绍】排列组合问题汇总
文章总览：远行雪杖的清晨排列组合，这是初赛题目和复赛数学题目中必不可少的一部分，同时也是大多数计数类 DP 的重难点所在。其特点就是各种题目百出不厌，千变万化，让人措不及防，但是实际上中国有句古话叫做“万变不离其宗”，排列组合的问题也是有一定套路可言的。本篇文章旨在总结大多数类型的排列组合基础模型以及使用方式，排列组合问题计算时几个常见的思考方向，等等等。下为文本大纲：
组合数基础
二项式定理
隔板法基础
组合数例题
排列数基础
错位排列
圆排列
多重集合排列
康托展开
排列组合综合应用
组合基础：便携炉具的正午
组合数基础
二项式定理
隔板法基础
组合数基础推导组合数大家绝对不陌生，组合数指的就是 $n$ 个数里面选出 $m$ 个，不考虑取出的顺序，有几种取法，这个取法的方法数量就是大家常见的 $C_n^m$。
举个最常见的例子，我有 $6$ 个数字，我要从中选出 $3$ 个，那么他表示成刚刚的符号就是 $C_6^3$，但是问题是如何计算呢？非常显然的，如果我们考虑取数的顺序，那么计算出来的就是排列数，我们划去排列即可。
具体的，第一个数字有 $6$ 种取法，第二个数字就少了一 ...
【算法介绍】中国剩余定理及其拓展
文章总览：穷高极天，亢盈难久中国有句古话：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”上过小学一年级的我们都知道，这是非常经典的同余方程组，而它的解法，就是这篇文章要讲的中国剩余定理 $\tt Chinese\ Remainder\ Theorem$。
本文内容限定于下：
中国剩余定理证明
中国剩余定理实现
拓展中国剩余定理证明
拓展中国剩余定理实现
推导其一：威制八毒，灭却炎烟
同余方程的计算&通解形式
通解形式正确性证明
从实例出发的推导那么从开篇提到的“物不知数”问题出发，我们可以得到下面的同余方程组：
\begin{cases}
x\equiv 2\pmod 3\\
x\equiv 3\pmod 5\\
x\equiv 2\pmod 7
\end{cases}其实这个题目很早就有了答案，“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。”这是来自于明朝数学家程大位在《算法统宗》中的解答口诀。其含义即是关于这个问题的通解形式，其中第一个字的表示模数，最后一个词中的数字表示每一个同余方程余数要乘以的系数，最后加起来模 $10 ...
517九段第三课 A ：整数分块 again
题面：整数分块again大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
给出 $N$ 并计算下面表达式的值：
\sum_{i=1}^N i^4\left\lfloor\frac{N}{i}\right\rfloor答案对于 $M$ 取模。
思路拿到题面，注意到整数分块的经典部分，不难写出如下代码：123456789inline void Work() { ll ans = 0; for(ll l = 1, r = 1; r <= n; l = r + 1) { r = n / (n / l); (ans += ((f(r) - f(l - 1) + P) % P) * (n / l) % P) %= P; if(r == n) break; } printf("%lld\n", ans);}
那么这题主要的考点，其实就是计算一段区间内的四次方和。借助强大的搜索引擎我们可以轻松知道四次方和前缀和公式是：
\cfrac{n(n+1)(2n+1) ...
517九段第一课 E ：求和
题面：不互质的数大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
对于给定的 $N$，定义 $S(k)$ 为 $(x_1,x_2,…,x_k)$ 的数量。$(x_1,x_2,…,x_k)$ 满足以下条件：
$(x_1,x_2,…,x_k)$ 为正整数
$x_1+x_2+…+x_k=N$
现在需要你找到 $(S(1)+S(2)+…+S(N)) \bmod 10^9+7$
思路不难注意到对于 $N$ 而言 $S(k)=C_{N-1}^{k-1}$，我们要求的式子就可以化为 $\sum_{i=0}^{N-1}C_{N-1}^i=2^{N-1}$。但是 $N$ 特别大，大到需要高精度怎么办？快速幂显然不行，注意到 $2^{P-1}=1\pmod P$ 所以不断地从 $N$ 中提取出 $P-1$ 即可。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<bits/stdc++.h>using namespa ...
517九段第一课 D ：不互质的数
题面：不互质的数大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
求 $1\sim N-1$ 中与 $N$ 不互质的数的和并对 $1e9+7$ 取模。
思路注意到 $k$ 与 $N$ 互质时，$N-k$ 也与 $N$ 互质，满足对称性，则利用类似等差数列求和的思路，可得 $n\times \varphi(n)/2$ 就是与 $N$ 互质的数的和，从总量减去即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc++.h>using namespace std;typedef long long ll;// typedef __int128 int128;typedef pair<int , int > pii;typedef unsigned long long ull;namespace FastIO { ...
517九段第一课 B ：解方程
题面：解方程大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
计算关于 $x, y$ 方程 $Ax+By+C=0$ 满足 $x_1\le x \le x_2,y_1\le y\le y_2$ 的整数解有多少个，其中给出 $A,B,C,x_1,x_2,y_1,y_2$ 并保证 $x_1\le x_2,y_1\le y_2$。
思路注意到方程可以化简为 $Ax+By=-C$，拓展欧几里得可以解决问题 $Ax+By=\gcd(A,B)$ 的问题，所以将方程中的未知数整体提取 $\frac{-C}{\gcd(A,B)}$，拓欧解出特解后乘回去，最后通过拓欧一般解计算公式
x = x_0 + \cfrac B {\gcd(A,B)} \times k ,y = y_0 - \cfrac A {\gcd(A,B)} \times k\quad(k ∈ Z)最后计算出合理的新的 $x,y$ 上下界即可。
关于无解和特解情况看代码。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243 ...
【算法介绍】网络流相关
算法总览：散勇化晓摸幺鱼简单的来说，网络流问题，就是给出一张图，图上面有一个起点，被称作“源点”，还有一个终点，被称作“汇点”。而每一条边都有一个容量，超过容量就不可以通过这条边，有时候边还会有费用，通过这条边就需要花费这些费用。最终的目的就是从源点出发，不管你用什么方法走，最终汇集到汇点的流量最大、或者流量最大中的方案中费用最小的等等等等……这类问题，全都被称作为网络流问题或者流量问题，在生活中应该是非常常见的一种问题。
本文内容限定大纲如下：
网络流整体简介与符号规定
网络流经典问题类型
残量网络的定义
增广路与反向弧
最大流计算之 $\tt FF$ 方法
最大流计算之 $\tt EK$ 算法
最大流计算之 $\tt Dinic$ 算法
最大流计算之 $\tt Dinic$ 算法优化
最小割计算之最大流最小割定理
最小割计算之割集与变种
费用流计算之算法推导
算法基础：棋秤作枕好入眠
网络流整体简介与符号规定
网络流经典问题类型
残量网络的定义
增广路与反向弧
网络流基本概念OK啊各位，虽然一开始的文章总览提到了网络流问题的基础概念，但是这里还是补充一下详细的定义以及一些符号 ...