题解
枚举容斥原理
题意
定义 $f(i)$ 为非 $i$ 因子的最小正整数，现给出正整数 $n$ ，求 $\sum_{i=1}^nf(i)$ 对 $10^9+7$ 取模后的值。
$n\leq10^{16}$ 。
题解
傻逼题。枚举每个 $f(i)$ 的贡献即可。要容斥掉已经统计的部分。复杂度大概 $\mathcal{O}(1)$ 。
代码
const int N = 1, mod = 1e …
Jayun 发布于 2023-11-06 16:17:57
00
容斥原理
题意
小 Ω 在小学数学课上学到了“幂次”的概念： $\forall a, b \in \N^+$ ，定义 $a^b$ 为 $b$ 个 $a$ 相乘。
她很好奇有多少正整数可以被表示为上述 $a^b$ 的形式？由于所有正整数 $m \in N^+$ 总是可以被表示为 $m^1$ 的形式，因此她要求上述的表示中，必须有 $b \geq k$ ，其中 $k$ 是她事先选取 …
Jayun 发布于 2023-11-05 20:19:08
00
斯特林数组合意义树形动态规划（树形 DP）排列组合
题意
给出一棵树和一个常数 $m$ ，对于每一个 $i~(1\leq i\leq n)$ ，求 $\sum_{j=1}^n\text{dist}(i,j)^m$ 。
题解
关于斯特林数有性质 $x^n=\sum_{i=1}^n\frac{x!}{(x-i)!}\begin{Bmatrix}n\\i\end{Bmatrix}$ ，组合意义相当于枚举非空盒。
则原题有，
$$\sum_{k=1 …
Jayun 发布于 2023-11-04 22:46:52
00
容斥原理斯特林数快速数论变换（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