# 【树状数组，区间最值】P2880 [USACO07JAN] Balanced Lineup G ## 题意概括 给定 $n$ 头牛的身高 $h_1,h_2,\dots,h_n$，有 $q$ 次询问。 每次询问给出区间 $[l,r]$，要求输出这个区间内最高牛和最低牛的身高差，也就是： $$...

# 【树上统计，组合数学】Select from Subtrees # 题意概括 给定一棵 $N$ 个节点的有根树（根为 1）。每个节点 $i$ 初始有 $C_i$ 个不同的糖果。 有 $N$ 只松鼠，第 $i$ 只松鼠需要从以 $i$ 为根的子树中挑选 $D_i$ 个糖果。不同松鼠不能选同一个糖果，不同松鼠选到相同的糖果组合视为不同的分配方案。...

| 序号 | 题号 | 题目名称 | 标签 | 难度 | |---:|---|---|---|---| | 1 | [B3941](https://www.luogu.com.cn/problem/B3941) | [GESP样题 五级] 小杨的锻炼 | 数论最大公约数 gcd | 普及− | | 2 |...

# 【广度优先搜索，枚举】假期计划 # 题意概括 给定一张 $N$ 个点、$M$ 条边的无向连通图，点 1 代表家。需要挑选 4 个互不相同的景点，依次记为 A、B、C、D。要求在 $1 \to A \to B \to C \to D \to 1$ 的 5 段行程中，每段行程经过的最短边数不能超过 $K+1$。每个景点都有一个固定的分数，求 A、B、C、D...

# 【区间DP】算式 # 题意概括 给出 $n$ 个相对位置固定的非负整数，要求在这些数字之间填入 $k$ 个乘号和 $(n-k-1)$ 个加号。你可以通过任意添加括号来改变运算顺序，目标是找到一种运算安排，使得最终计算出的表达式结果最大。 数据保证 $2 \le n \le 15$，$0 \le k < n$，给定数字都在 $0$ 到 $9$...

# 题意概括 给定 $m$ 个完全相同的乒乓球和 $n$ 个不同的盒子。第 $i$ 个盒子最多只能放入 $a_i$ 个乒乓球。求将这 $m$ 个球全部分配到 $n$ 个盒子中的合法方案数。由于结果可能很大，输出方案数对 1000000007 取模的结果。 假设本题的数据范围为 $n, m \le 2000$，$0 \le a_i \le m$。输入的第一行为...

# 【贪心】P4447 [AHOI2018初中组] 分组 # 题意概括 给定 $n$ 个队员的实力值，需要将他们分成若干个小组。要求每个小组内的实力值必须是连续的整数，且同一个组内不能出现相同的实力值。每个队员都必须恰好分入一个小组。求在所有合法的分组方案中，人数最少的小组人数的最大值。 输入第一行是一个正整数 $n$；第二行包含 $n$...

```cpp #include using namespace std; using ll = long long; bool f[100005]; void mkk() { fill(f + 2, f + 100005, true); for (int i = 2; i * i <= 100000; i++) { if (f[i]) { for (int...

## 什么是 NTT NTT，全称是 Number Theoretic Transform，中文通常叫“数论变换”。 它可以理解为： > 在模意义下进行的 FFT，用来快速计算多项式乘法，也就是卷积。 普通的多项式乘法是 $O(n^2)$ 的，而 NTT 可以把复杂度降到 $O(n\log n)$。 ## NTT 解决什么问题 假设有两个多项式： $$...

## 什么是两类斯特林数 斯特林数是组合数学中用来描述“把元素组织成若干部分”的一类计数工具，常见的有两类：**第一类斯特林数**和**第二类斯特林数**。 它们名字相近，但数的对象完全不同： - 第一类斯特林数：数的是**排列可以分成多少个循环**； - 第二类斯特林数：数的是**集合可以分成多少个非空子集**。 ## 第一类斯特林数...