FallenLeaf's Blog

Content：生成函数，多项式，期望 Date：2025.8.1 课堂内容 生成函数 定义 普通生成函数（OGF）：普通生成函数的定义为形式幂级数：F(x)=∑iaixi\displaystyle F(x) = \sum_{i} a_i x^iF(x)=i∑​ai​xi 指数生成函数（EGF）：指数生成函数的定义为形式幂级数：F(x)=∑iaixii!\displaystyle F(x) = \sum_{i} a_i \frac{x^i}{i!}F(x)=i∑​ai​i!xi​ 普通生成函数的基本运算 F(x)±G(x)=∑i(ai±bi)xi\displaystyle F(x) \pm G(x) = \sum_{i} (a_i \pm b_i) x^iF(x)±G(x)=i∑​(ai​±bi​)xi F(x)G(x)=∑nxn∑i=0naibn−i\displaystyle F(x)G(x) = \sum_{n} x^n \sum_{i=0}^n a_i b_{n-i}F(x)G(x)=n∑​xni=0∑n​ai​bn−i​ 封闭形式。e.g. F(x)=∑n≥0x...

Content：组合数学 Date：2025.7.31 课堂内容 容斥原理 其主要思想为：把禁止违反哪些规则改为钦定违反了哪几条规则，并赋予 (−1)k(-1)^k(−1)k （即违反 kkk 条规则）的容斥系数。 二项式反演 g(n)=∑i=0n(ni)f(i)⇔f(n)=∑i=0n(−1)n−i(ni)g(i)g(n)=∑i=nN(in)f(i)⇔f(n)=∑i=nN(−1)i−n(in)g(i)\begin{aligned} g(n) &= \sum_{i=0}^n \binom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} g(i) \\ g(n) &= \sum_{i=n}^N \binom{i}{n} f(i) \Leftrightarrow f(n) = \sum_{i=n}^N (-1)^{i-n} \binom{i}{n} g(i) \end{aligned} g(n)g(n)​=i=0∑n​(in​)f(i)⇔f(n)=i=0∑n​(−1)n−i(...

Content：数论 Date：2025.7.30 课堂内容 莫比乌斯函数 定义如下： μ(n)={1n=1(−1)kn=p1p2p3…pk,∀pi∈P0otherwise\mu(n) = \begin{cases} 1 & n=1 \\ (-1)^k & n = p_1 p_2 p_3 \dots p_k, \forall p_i \in P \\ 0 & otherwise \\ \end{cases} μ(n)=⎩⎨⎧​1(−1)k0​n=1n=p1​p2​p3​…pk​,∀pi​∈Potherwise​ 其中莫比乌斯函数有如下性质： ∑d∣nμ(d)=[n=1]\sum_{d|n} \mu(d) = [n=1] d∣n∑​μ(d)=[n=1] 欧拉函数 定义如下： φ(n)=∑i=1n[gcd(n,i)=1]\varphi(n) = \sum_{i=1}^n [gcd(n,i)=1] φ(n)=i=1∑n​[gcd(n,i)=1] 其中欧拉函数具有如下性质： ∑d∣nφ(d)=n\sum_{d|n} \varphi(d) = n d∣n∑​φ(...

New Beginning, New Future 也是用 Github Page 搭建了一个新的博客。 最近应该会把博客园的文章搬运过来（搬完了喵~），继续加油吧。

Content：平衡树 Date：2025.7.29 具体内容 Leafy Tree 和 Un-leafy Tree Leafy Tree：表示将所有的数据存放在叶子节点的树形数据结构，类似 线段树 和 WBLT 平衡树。 Un-leafy Tree：与 Leafy Tree 相反，将数据存放在每个树节点的数据结构。 替罪羊树 替罪羊树是最简单的平衡树，也是 Un-leafy 的，其核心思想是定义一个常数 α\alphaα，对于树上任意节点 uuu，若 max⁡(sizlsu,sizrsu)≥α×sizu\max(siz_{ls_{u}}, siz_{rs_{u}}) \ge \alpha \times siz_umax(sizlsu​​,sizrsu​​)≥α×sizu​，则将整棵树拍平成数组，对整棵树重构，使其保持平衡性。 替罪羊树的复杂度是 O(nlog⁡n)O(n \log n)O(nlogn) （均摊）的，同时 α\alphaα 的取值对复杂度的影响是直接的，当 α\alphaα 在区间 [0.5,1][0.5,1][0.5,1] 之间时，复杂度时最优的，一般取 α=...

Content：模拟赛 Date：2025.7.28 Problem-A 排序 题目大意 优化程序： #include <algorithm>#include <cmath>#include <iostream>const int N = 3e7 + 5;int n, seed;double a[N];void gen_input(const int n, const int seed) { double x = (double)(seed); unsigned int iseed = seed; for (int i = 0; i < n; ++i) { iseed = iseed * 1664525 + 1013904223; x = (std::sin(iseed % 4096) + 1) / 2; a[i] = std::fabs(x * (iseed >> (iseed % 30))) + 1e-9; }}int main() { std...

Content：矩阵 DP Date：2025.7.27 Review 矩阵基本操作：link Example1 - 洛谷-P1962 斐波那契数列 题目描述 给定 nnn，求斐波那契数列的第 nnn 项 fnf_nfn​。 fn={1n=0,1fn−1+fn−2oterwisef_n = \begin{cases} 1 & n = 0,1 \\ f_{n-1} + f_{n-2} & oterwise \end{cases} fn​={1fn−1​+fn−2​​n=0,1oterwise​ 数据范围：n<263n < 2^{63}n<263。 思路 首先显然 O(n)O(n)O(n) 的递推是不行的了，我们考虑将递推式转化为矩阵乘法的形式： [fn−1fn−2]×[1101]=[fnfn−1][fn−2fn−3]×[1101]2=[fnfn−1]…[f0f1]×[1101]n−2=[fnfn−1]\begin{aligned} \begin{bmatrix} f_{n - 1} \\ f_{n - 2} \end{bmatrix}...

Content：dp优化 Date：2025.7.26 例题 洛谷-P1886 滑动窗口 思路 直接单调队列维护即可，具体操作如下： 每次查看队尾的元素，维护单调性。 对于队头不在当前滑动窗口的元素，弹出。 提交记录：link 洛谷-P2365 任务安排 思路 定义 dpidp_{i}dpi​ 表示第 iii 个任务完成所花费的最小代价。转移如下： dpi=min⁡1≤j≤idpj+(s+Ti−Tj−1)×(Fn−Fj−1)dp_{i} = \min_{1 \le j \le i} dp_{j} + (s + T_i - T_{j-1}) \times (F_{n} - F{j - 1}) dpi​=1≤j≤imin​dpj​+(s+Ti​−Tj−1​)×(Fn​−Fj−1) 对于本题数据范围 n≤3000n \le 3000n≤3000，O(n2)O(n^2)O(n2) 可过。 提交记录：link 洛谷-P10979 任务安排 2 思路 dpdpdp 的方式和定义与前面相同，但是 O(n2)O(n^2)O(n2) 的复杂度无法接受，所以考虑优化。 将 dpdpdp 的式子...