题解
容斥原理斯特林数快速数论变换（NTT）组合意义
第二类斯特林数·行
题目描述
输出 $\begin{Bmatrix} n \\0 \end{Bmatrix},\begin{Bmatrix} n \\1 \end{Bmatrix},\begin{Bmatrix} n \\2 \end{Bmatrix},\dots,\begin{Bmatrix} n \\n \end{Bmatrix}$ 的值。
$1\leqslant n\leqslant 2\ …
Jayun 发布于 2023-11-03 11:57:26
00
博弈树形动态规划（树形 DP）
题意
给定一棵树，初始时非叶节点均为无色，叶节点会是红色、蓝色或无色。小红和小蓝轮流给无色叶子染色（小红染红色，小蓝染蓝色，小红先染）。所有叶子染完后，非叶节点的颜色将被逐一确定：一个非叶节点的颜色是它所有儿子的颜色中出现较多的那个（保证有奇数个儿子）。最后，根是谁的颜色谁就获胜。求小红是否能赢，若能赢，求出第一步选择哪些叶子能赢。
$n\leq10^6$ 。
题解
一个点有四种情况：
必红。 …
Jayun 发布于 2023-11-02 17:13:53
00
树形动态规划（树形 DP）计数
题意
给定整数序列 $A$ ，要构造一个数列 $B$ ，其中 $B$ 由 $0, 1$ 组成，且 $0$ 的个数等于 $1$ 的个数。
在此前提下，构造一个数列 $B$ 使得 $\sum_{i=2}^n A_i*(B_i \otimes B_{\left\lfloor\frac{i}{2}\right\rfloor})$ 最大。输出这个值的最大可能值。
其中， $\ot …
Jayun 发布于 2023-11-02 17:01:29
00
全局平衡二叉树树形动态规划（树形 DP）
【模板】"动态 DP"&动态树分治
题目描述
给定一棵 $n$ 个点的树，点带点权。
有 $m$ 次操作，每次操作给定 $x,y$ ，表示修改点 $x$ 的权值为 $y$ 。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
$1\le n,m\le 10^5$ ， $1 \leq u, v , x \leq n$ ， $-10^2 \leq a_i, y \le …
Jayun 发布于 2023-11-02 08:20:11
00
计数矩阵快速幂容斥原理
题意
一个无向图， $n$ 个点 $m$ 条边。
需要构造长度为 $d$ 的序列，要求必须包含 $[1,k]$ 的点，且相邻项有边连接，相邻不相同，可以重复。求序列数量。
$1\le n \le 20, 1 \le m \le \min(150,n*(n-1)/2),0 \le k \le \min(n,7),1\le d \le 10^9$ 。
题解
考虑 $k=0$ 的情况 …
Jayun 发布于 2023-11-01 13:52:57
00
数学推导杂项
题面
给定 $n$ 个点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ ，求出 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}{((x_i-x_j)^2+(y_i-y_j)^2)}$ 。
$2\le n \le 10^5,|x| \le 10^5,|y| \le 10^5$ 。
题解
简单题。对于 $x$ ，式子变成 $\sum_{i=1 …
Jayun 发布于 2023-11-01 13:42:47
11
并查集吉司机线段树（势能分析线段树）
题面
有 $n$ 个容器，从最高层到最底层分别编号为 $1,2,\cdots,n$ 。
现在会在这些容器中倒上一些香槟，当第 $i$ 层容器倒满时，多余的香槟会流到第 $i+1$ 层中，如果第 $n$ 层容器也满了香槟就会流到外面去。第 $i$ 层容器的容量为 $a_i$ ，不保证 $a$ 递增。
你需要实现下面两种操作 $q$ 次：
往某一个编号为 $x$ …
Jayun 发布于 2023-11-01 13:28:08
00
枚举区间动态规划（区间 DP）朴素模拟
题意
给一段程序：
int qsort(int L, int R) {
if (L >= R) return 0;
int i = L, j = R;
int x = Random.Next();
int x0 = A[x];
assert(L <= x && x <= R);
while (i < j) {
while (A[i] < …
Jayun 发布于 2023-11-01 07:20:17
00
博弈树形动态规划（树形 DP）二分答案
题意
给定两个人的树上博弈规则。小 N 初始时在节点 $S$ ，小 Y 需要通过一些操作“强迫”小 N 最后到达节点 $T$ 。小 N 想要让小 Y 的操作尽量多，而小 Y 希望自己的操作尽量少。求解两人都采取最优决策时，小 Y 的操作次数。 每一轮中操作如下：
小 Y 可选的操作有：恢复一条小 N 删除的边 ；或者删除一条边；或者跳过这次操作（不计入答案）。
小 N 接下来执行：如果 …
Jayun 发布于 2023-10-31 21:21:25
00
李超线段树
题目描述
要求在平面直角坐标系下维护两个操作：
在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$ 。
给定一个数 $k$ ，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。
强制在线。
题解
李超树板题。在点上维护线段。
代码
const int N = 100005;
const int mod = 39989;
const double …
Jayun 发布于 2023-10-31 15:59:30
00