A - Omkar and Password 签到题。如果全部相同则无法合并，答案为 n；否则用某个最大的元素和相邻元素不断合并即可，答案为 1。 B - Omkar and Infinity Clock 签到题。设初始…

A - Road To The 3rd Building 按区间长度对区间分组，分别计算每组区间对于答案的贡献。设该组区间的长度均为 L，考虑位置 i 被多少个区间覆盖，设为 a_i，发现序列 a_1\dots a_n …

前言 矩阵树定理可以统计无向图的生成树个数或所有生成树权值之和，以及有向图的根向/叶向树形图个数或所有树形图权值之和 其中，一个生成树/树形图的权值定义为其所有边的边权之积 p.s. 以下内容均默认可以有重边（视为不同的…

Luogu P3381 【模板】最小费用最大流 #include <iostream> #include <stdio.h> #include <string.h> #include <vecto…

Luogu P3389 【模板】高斯消元法 #include <iostream> #include <stdio.h> #include <string.h> #include <math.h>…

前言 扩展Lucas定理适用于大数组合数取模，且模数不一定为质数的情况 求解 Step 1 若 n,m 为非负整数，n\ge m，p 为任意正整数。现在要求的是 C_n^m\bmod p 首先将 p 分解为质因子的幂之积…

定义 对于非负整数 n,m 和素数 p，设 n,m 在 p 进制下的展开为： n=\sum_{i=1}^k n_ip^{k_i}\\m=\sum_{i=1}^k m_ip^{k_i}\\ 则有同余式： C(n,m)\eq…

定义 对于正整数 n，其欧拉函数为小于等于 n 的正整数中与 n 互质的数的个数，记为 \varphi(n) 性质与定理 基本性质 设 p 为任意素数，则有以下性质： \varphi(p)=p-1 \varphi(p^k…

前言 扩展中国剩余定理（exCRT）适用于求解模线性方程组，且模数不一定两两互质的情况 求解 两个方程 先考虑只包含两个方程的模线性方程组： \begin{cases} x\equiv b_1\pmod{a_1}\\ x…

前言 中国剩余定理可以用来求「模线性方程组」的解，即： \begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\\ x\equiv b_n…