普通生成函数(OGF)

.center { margin-left: auto; margin-right: auto; display: table; width: auto; } 介绍 生成函数可以解决形如 满足XX条件的方案数共有多少种 的问题,它也能够解决 推导通项公式 等问题,生成函数常常与多项式运算

多项式全家桶

模版 多项式全家桶 #include <bits/stdc++.h> using namespace std; const int mod = 998244353; const int maxn = (1<<22) + 5; struct NTT { const ll g = 3, invg = inv(g); // mod = 998244353 inline ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a

NTT

模版 NTT const int mod = 998244353; const int maxn = (1<<22) + 5; struct NTT { const ll g = 3, invg = inv(g); // mod = 998244353 inline ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } inline

FFT

.center { margin-left: auto; margin-right: auto; display: table; width: auto; } 模版 FFT const int maxn = (1<<22) + 5; // 注意这里需要是 > 2^k struct Complex { double x,y; Complex(double _x = 0.0, double _y = 0.0) { x = _x; y = _y; } Complex operator+(const Complex& b) const { return Complex(x + b.x, y + b.y); } Complex operator-(const Complex& b)

线性基

介绍 线性基是一般用于解决 子集XOR,XOR最值 一类问题的算法。 定义 线性基是一个 linear space,在这个space中,所有的向量为 非负整数,而 scalar 则

高斯消元

介绍 高斯消元是矩阵操作里最基础的一个,主要用于解形如 $a_1x_1 + a_2x_2 + a_3x_3 = b_1$ 之类的线性方程组。 步骤 按 column 进行遍历 遍历到第 $k$ 个 column 时,在这个column中,

概率期望

例1 洛谷P1850 [NOIP2016 提高组] 换教室 题意 有 $n$ 个时间段,每个时间段有 $2$ 节课程。其中在时间段 $i$ 的两节课,分别在教室 $c_i, d_i$ 上。 对于所有的时间段 $i$,

网络流

介绍 网络 是一个有向图 $G = (V,E)$,每条边 $(u,v) \in E$ 都拥有一个容量 $c(u,v)$。 在一个网络中,拥有两个特殊的节点 $s, t$ (源点,汇点)。 定义 流

二分图 & 二分图匹配

二分图 - 定义 二分图是一种特殊的无向图,可以将点集划分为两部分,在同一集合中的节点之间没有 edge。 二分图 - 性质 二分图 $\iff$ 图中没有奇环(指节点个

换根DP

介绍 换根DP是一种特殊的树形DP。主要特点在于需要进行两次DFS。 第一次DFS:固定任意节点(一般为 $1$)为根。对于每一个节点 $u$,仅考