ffacs 的博客
  文章分类
算法 14 python笔记 3 笔记 12 solution 3 Golang笔记 13 icpc 3
网络流 网络流
流网络 \(G=(V,E)\) 是一个有向图，图中每条边 \((u,v,)\in E\) 有一个非负的容量值 \(c(u,v)\geq 0\) ,而且，如果边集合 \(E\) 包含一条边 \((u,v)\) ，则图中不存在反方向的边 \((
2021-01-12 算法
网络流 图论 最大流
叉积 叉积
意义 假设给了我们两个向量\(\left[x_1\ y_1\ z_1\right],\left[x_2\ y_2\ z_2\right]\)，我们有一个函数 \[ f(\left[x\ y\ z\right])=det \left( \le
2021-01-12 算法
数学 线性代数 计算几何
最短路 最短路
Floyd Floyd 算法可以用来求解全局最短路径问题。即求出任意结点 \(v\) , \(w\) 的最短路长度。时间复杂度为 \(O(V^3)\) 。 算法原理 假设有向图 \(G\) 有 \(V\) 个点，Floyd算法采用的是动态规
2021-01-12 算法
图论 最短路
最大权闭合子图 最大权闭合子图
定义 设一个图 \(G=(V,E)\) 的闭合图 \(G'=(V',E')\) ，满足对 \(\forall v \in V'\) 引出的 \(\forall \left<s,u\right>\i
2021-01-12 算法
网络流 最小割 最大权闭合子图 图论
CDQ分治 CDQ分治
逆序对-梦开始的地方 题目: 给定序列\(s,|s|\leq 1e5\),求序列中逆序对的数量 一种解法当然是离散化以后用树状数组求啦. 另外一种方法就是 归并排序 ,采用分治的思想,一个区间中全部的逆序对数等于左区间的逆序对数+右区间的逆
2021-01-12 算法
分治
欧拉函数 欧拉函数
在数论中，对 正整数 \(n\), 欧拉函数 \(\phi(n)\) 是 小于等于 \(n\) 的正整数中与 \(n\) 互质的数的数目。 求欧拉函数值 首先我们考虑素数的欧拉函数值，素数肯定与小于本身的正整数互质，所以 \(\phi(p)
2021-01-12 算法
数学 初等数论
FFT FFT
点值表示法 \(n\) 个二维平面上的点 \((x_1,y_1)…(x_n,y_n)\) ，确定了唯一一个过这些点的 \(n-1\) 次多项式。 证明:设 \(n-1\) 次多项式 \(f(x),g(x)\) 都经过这 \(n\) 个点，设
2021-01-12 算法
多项式 卷积 复变函数 数学
NTT NTT
在 \(\text{FFT}\) 中，我们使用复数的单位根进行 \(DFT\)，这样会产生浮点数误差。对于只有整数参与的多项式运算，我们需要找到正好的方法。 引入 考虑 \(\text{FFT}\) 的时候我们为什么选择使用复数单位根。 \
2021-01-12 算法
多项式 卷积 数学 初等数论
素数无穷个的证明方法 素数无穷个的证明方法
方法 \(1\) 设: \(n \ge 0\), \(F_n=2^{2^n}+1(Fermat\ Number)\) ,设 \(n\neq m\) ,若 \(d > 1,d \mid F_n\) 则 \(d\) 不整除 \(F_m\)
2021-01-12 算法
数学 初等数论
最大公约数理论 最大公约数理论
定理 \(1\) \(a_j \mid c(1\le j\le k)\) 的充要条件是 \(\left[a_1,…a_k\right]\mid c\) 证明 充分性 \(a_j \mid \left[a_1,..,a_k\right],\l
2021-01-12 算法
初等数论 最大公约数
莫比乌斯反演 莫比乌斯反演
莫比乌斯函数 \[ \begin{aligned} \mu(n)=\left\{ \begin{array}{lr} 1 \qquad\qquad\qquad n=1\\ (-1)^k\qquad\qquad n为k个不同素数的乘积 \\
2021-01-12 算法
数学 初等数论
FWT FWT
引入 求 \[ \sum_{i=1}^n c_i=\sum_{j\oplus k=i} a_jb_k (n\le 1e5) \] 其中 \(\oplus\) 表示一种二元位运算 与、或 与、或的正变换 对于 按位或 运算，我们发现 \(i\
2021-01-12 算法
多项式 卷积 数学
1 / 2