A - Omkar and Password 签到题。如果全部相同则无法合并,答案为 n;否则用某个最大的元素和相邻元素不断合并即可,答案为 1。 B - Omkar and Infinity Clock 签到题。设初始…
分类:OI/ACM
【XJTU 2020暑期集训】Day1 - 2020 杭电多校训练第6场
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…
【学习笔记】扩展Lucas定理(exLucas)
前言 扩展Lucas定理适用于大数组合数取模,且模数不一定为质数的情况 求解 Step 1 若 n,m 为非负整数,n\ge m,p 为任意正整数。现在要求的是 C_n^m\bmod p 首先将 p 分解为质因子的幂之积…
【学习笔记】Lucas定理
定义 对于非负整数 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)
前言 扩展中国剩余定理(exCRT)适用于求解模线性方程组,且模数不一定两两互质的情况 求解 两个方程 先考虑只包含两个方程的模线性方程组: \begin{cases} x\equiv b_1\pmod{a_1}\\ x…
【学习笔记】中国剩余定理(CRT)
前言 中国剩余定理可以用来求「模线性方程组」的解,即: \begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\\ x\equiv b_n…