2024.8 做题记录

8.1

P6222

$an s = \sum_{T = 1}^{n} T^{k} S (\frac{n}{k}) \sum_{d ∣ T} d μ^{2} (d) μ (\frac{T}{d})$
令 $f (T) = \sum_{d ∣ T} d μ^{2} (d) μ (\frac{T}{d})$ ，为积性函数，讨论 $f (p^{k})$ 的取值。

P10636

枚举第一个点和第三个点的横纵坐标之差 $i, j$ ，第二个点有 $g c d (i, j) - 1$ 种选择。
$an s = \sum_{i = 1}^{n} \sum_{j = 1}^{m} (n - i) (m - j) (g c d (i, j) - 1)$
莫比乌斯反演。

8.3

对每个指数 min-max 容斥，乘起来得到 gcd-lcm 容斥。
$l c m (T) = \prod_{S \subseteq T} g c d (S)^{(- 1)^{∣ S ∣ + 1}}$
$f (n) = \frac{x ^{n + 1} - 1}{x - 1}$ 。提出 $x - 1$ 。因为 $g c d (x^{a} - 1, x^{b} - 1) = x^{g c d (a, b)} - 1$ ，用 map 储存指数。

8.6

arc069d

二分答案，线段树优化建图跑 2-sat。要保证 $i$ 不会连到 $i^{'}$ ，向排序后一个编号区间连边，中间挖空。

P10833

枚举每个 $a_{i} = 1$ 将序列划分开，枚举左/右端点，钦定最大值在左/右边，可以确定一段区间。随机异或哈希比较 $\oplus_{i = l}^{r} f_{a_{i}} = \oplus_{i = 1}^{r - l + 1} f_{i}$ 。

8.7

arc072d

模拟赛 T2。

设 $f_{i, j}$ 为前 $i$ 天体积为 $j$ 的最大质量，图像上凸。 $f_{i - 1}$ 到 $f_{i}$ 即删去 $[v_{i}, L]$ ，在最开始加上 $(v_{i}, v_{i} t_{i})$ ，在将前面取 max 为上凸。双端队列维护。

arc070c

模拟赛 T3。

设 $f_{i, j}$ 表示前 $i$ 条线段，第 $i$ 条左端点为 $j$ 的最小代价。 $f_{i, j} = min_{k = j - l e n_{i - 1}}^{j + l e n_{i}} f_{i - 1, j} + ∣ j - l_{i} ∣$ 。

取 min 和加绝对值函数，下凸，slope trick 维护。

模拟赛 T4

从小到大放入特殊点，当前在点 $i$ ，已选的比赛集合为 $s$ ，有 $j$ 个点在 $[1, a_{i}]$ 中没被选。每个和 $1$ 比赛的特殊点都是子树中最大的。dp 套 dp 维护上升子序列长度，做前缀最大值后差分后状压得 $t$ ， $t$ 是 $s$ 的子集。枚举没选过的比赛 $l$ ， $d p_{i, u p d (s, t, l) ， j + a_{i} - a_{i - 1} - 2^{l}} = d p_{i - 1, s, t, j} \times (2 ^{l} - 1 j + a _{i} - a _{i - 1} - 1) \times (2^{l})!$ 。

P3343

$n$ 个 $[0, 1]$ 之间的随机变量第 $k$ 小的为 $\frac{k}{n + 1}$ 。引入第 $n + 1$ 个随机变量 $x$ ，第 $k$ 小的数值等于 $x$ 比第 $k$ 小小的概率 $\frac{kn !}{( n + 1 )!}$ 。

$d p_{s, i}$ 表示选点集 $s$ ，连了 $i$ 条边，不连通的方案数， $d_{s}$ 为 $s$ 内部的边，连通的方案数为 $(i b _{s}) - d p_{s, i}$ 。枚举 $s$ 的子集 $t$ ， $d p_{s, i} = ((j b _{t}) - d p_{t, j}) \times (i - j b _{s \oplus t})$ 。枚举答案为第 $i$ 条边， $an s = \sum \frac{i}{m + 1} \times (\frac{d p _{U, k - 1}}{( k - 1 m )} - \frac{d p _{U, k}}{( k m )})$ 。

8.8

P9047

模拟赛 T3。

$d p_{u, 0/1/2/3}$ 表示 $u$ 子树并向上传长为 $0/1/2/3$ 的链的最大贡献。转移时背包 $f_{i, 0/1}$ 记录上传长度 $1$ 的儿子比上传长度 $3$ 的多多少，以及上传长度 $2$ 儿子的奇偶性。随机排列儿子，期望前缀和最大值是 $O (n)$ 级别的。

agc061c

选 $a_{i}$ 或 $(a_{i}, b_{i})$ 有被选过选 $b_{i}$ 。容斥，取最大的 $b_{l} < a_{i}$ 和 $a_{r} < b_{i}$ ， $(l, r]$ 间选法固定， $- d p_{l} \to d p_{r}$ 。

8.9

CF925E

链加，树剖 dfn 区间加，分块维护。先减去 $t_{i}$ ，维护 $> 0$ 的白点数量。

Q4815

点分治，树上依赖性背包， $d p_{i, j} = max (d p_{i + 1, j - 1} + a_{r n k_{u}}, d p_{i + s i z_{r n k_{i}}, j})$ 。如果一定要选 $r t, u$ ，就 $O (k)$ 合并在前序遍历 dfn 序在 $[df n_{u}, n]$ 中的背包和后序遍历 dfn 序在 $[1, df n_{u} - s i z_{u}]$ 的背包选出 $k - d e p_{u}$ 个数。当分治的区域小于 $k$ 时停止，复杂度 $O (nk lo g \frac{n}{k})$ 。

abc269h

树形背包写成生成函数形式， $f_{u} (x) = \prod_{v} f_{v} (x) + x$ 。分为重儿子和轻儿子贡献。分治 ntt 维护 $g_{u} (x) = \prod_{v \in so n (u), v \neq = s_{u}} f_{v} (x)$ ，所有轻儿子子树大小之和为 $O (n lo g n)$ 。重链上 $f_{u} (x) = g_{u} f_{s_{u}} (x) + x$ 。只需要知道链顶的值， $f_{a_{1}} (x) = g_{a_{1}} (g_{a_{2}} (\dots (g_{a_{k}} + x) \dots) + x) + x = (\sum_{i = 1}^{n - 1} x \prod_{j = 1}^{i} g_{a_{j}}) + x$ 。分治 ntt 维护前缀乘积之和和乘积。复杂度 $O (n lo g^{3} n)$ 。

hdu7503

树形背包写成生成函数形式， $f_{u} (x) = \prod_{v} f_{v} (x) + 1$ 。特别的，需要求出重链上所有 $f_{u} (x)$ 每项的系数和，即 $g_{u} (x)$ 的区间乘积之和。分治 ntt 维护前缀乘积之和、后缀乘积之和、乘积和区间乘积之和。

8.10

cf rmj 暴毙！

CF1733E

模拟赛 T3。

$t$ 时刻可能在 $(x, y)$ 的是 $t - x - y$ 出发的人。设 $d p_{t, i, j}$ 表示前 $t$ 个人会经过 $(i, j)$ 几次， $d p_{i, j} = ⌈ \frac{d p _{i, j - 1}}{2} ⌉ + \frac{d p _{i - 1, j}}{2}$ 。差分看 $d p_{t, x, y} - d p_{t - 1, x, y}$ 是否为 $1$ 。

Q6815

模拟赛 T4。

线段树维护 $max a_{i}, \sum a_{i}, \sum max_{j = l}^{i} a_{j}, \sum a_{i} \times max_{j = l}^{i} a_{j}$ 。 $O (lo g n)$ 线段树上二分的 pushup。区间加和区间覆盖。线段树上二分。

8.11

arc182c

思路

有 $6$ 个小于 $14$ 的质数，设这 $6$ 个质数的指数分别为 $x_{1}, \dots, x_{6}$ 。 $an s = \sum (\prod_{i = 1}^{d} (x_{i} + 1))$ 。状压这 $6$ 个数，维护 $v a l_{s} = \prod_{i = 1}^{6} (x_{i} \times [s 二进制第 i 位为 1] + [s 二进制第 i 位为 0])$ 。当加入一个数时，某些 $x_{i}$ 会加 $d$ ， $s$ 二进制第 $i$ 位为 $1$ 的 $v a l_{s}$ 会从 $s$ 的子集且一些二进制第 $i$ 位为 $0$ 的 $t$ 的 $v a l_{t}$ 转移来。

8.12

模拟赛 T3

设 $f_{i}$ 表示当前有 $i$ 种状态的期望次数。 $f_{i} = i + \frac{f _{ik mod n}}{k}$ 。转移有环，设 $f_{i} = a_{i} f_{m + 1} + b_{i}$ ，递推 $a_{i}, b_{i}$ ，找到 $a_{p} = a_{m + 1}$ 可以计算 $f_{p}$ 真正的值， $f_{1} = a_{1} \times f_{p} + b_{1}$ 。

P8996

让前缀最大值 $a_{l}$ 代表整个区间，可以看做合并是将两个序列的前缀最大值排序。每次合并相当于在 $\frac{n}{2}$ 处断开跨过序列中点的区间 $[l, r]$ ，然后再重新按区间左端点的值排序。最多操作 $n$ 次，最多 $n$ 种区间。将询问离线，维护每次合并后的区间信息。建权值线段树表示前缀最大值 $l$ 代表的区间长度之和。

P8997

按题意模拟，用栈建出二叉树，叶子节点是要填的值，非叶子是运算符。

判断一个叶子能贡献能填哪些数并最终成为答案，设 $d p_{u, 0/1, 0/1}$ 表示 $u$ 子树内， $u$ 处的值 $\leq an s$ 或 $> an s$ ， $n u m 0$ 或 $n u m 1$ 最少为多少。根据 $u$ 处的运算符分类讨论转移。对于每个叶子算限制，只与从根到 $u$ 的 dp 值有关。可以发现放在一个叶子的答案是一个区间 $[n u m 0 + 1, n - n u m 1]$ ，差分维护区间加，最后计算大于 $0$ 的位置数。

8.13

模拟赛 T3

合并连续段写为二元组 $(a_{i}, t_{i})$ 。每次找到区间最小值合并，如果 $c_{i}$ 为奇数，一定不可能被跨过，写为 $(a_{i} + 1, \frac{t _{i}}{2}), (in f, 1), (a_{i} + 1, \frac{t _{i}}{2})$ 。线段树维护。

8.14

arc080d

模拟赛 T4。

将 $a$ 数组差分，得到 $2$ 倍连续段个数个 $1$ ，一次操作形如 $a_{i}$ 和 $a_{i + p r im e}$ 同时异或 $1$ 。 $i$ 向 $i + p r im e$ 连边，即为 $0 \to ∣ u - v ∣$ 的最短路。由哥德巴赫猜想， $1 0^{7}$ 内 $> 4$ 的偶数可以写成两个质数之和， $2 = 0 + 5 - 3$ ， $4 = 0 + 7 - 3$ ，所以所以 $0$ 到偶数 $i$ 的最短路为 $2$ 。如果 $i$ 为奇质数，最短路为 $1$ ；否则 $i + 3$ 为偶数，最短路为 $3$ 。

现在要将 $2 \times n u m$ 个数两两分组，代价为 $1/2/3$ ，最小化代价和。当选完若干个代价为 $1$ 的组时，奇偶性相同组的代价为 $2$ ，尽量匹配，代价为 $3$ 的至多只有一组。所以最大化代价为 $1$ 的组数。代价为 $1$ 时 $u, v$ 奇偶性不同，等于二分图最大匹配，网络流即可。复杂度 $O (n^{2} n + x_{i})$ 。

abc216h

概率转为方案数除以 $2^{nm}$ 。由 LGV 引理， $an s = \sum_{p} (- 1)^{σ (p)} \prod e (i, p_{i})$ 。 $e (i, j)$ 为 $m$ 步选 $j - x_{i}$ 步向前走。设 $d p_{s, i}$ 表示选了 $s$ 里的终止点，终止点 $\leq i$ 的方案数。

agc034d

最大化曼哈顿距离，拆绝对值变成 $4$ 个 $x_{i}, y_{i}$ 独立的式子。只要匹配的点对选的同一种式子即可。最小费用最大流。

8.15

【模板】矩阵求逆

将矩阵和单位矩阵放在一起高斯消元，把左边的矩阵消为单位矩阵时右边的单位矩阵变成逆矩阵。

模拟赛 T3

求 $x$ 使得 $n \times n$ 的矩阵 $A^{x} = C$ 。

$d e t (A) d e t (B) = d e t (A B)$ 。对 $d e t (A)^{x} \equiv d e t (C) (mod 1 0^{9} + 7)$ 做 BSGS。对于 $1$ 个可能的 $x$ ，判断 $x, x + m o d - 1, x + 2 \times (m o d - 1), \dots$ 。只有 $\frac{1 0 ^{10}}{m o d}$ 个 $x$ ，复杂度 $O (m o d + \frac{1 0 ^{10}}{m o d} n^{3})$ 。

8.17

模拟赛 T2

$an s \times n^{m} = \sum_{i = 1}^{n} (n - 1)^{a} i^{b} (n - i + 1)^{c} \times v a l (s_{k}, i) \times n^{m - k}$

是关于 $i$ 的 $m + 1$ 次多项式，维护 $m + 2$ 个点值插值。

模拟赛 T3

对于每个连通块，二分图染色分为 $a_{i}$ 和 $b_{i}$ 个点。每次要么选 $a_{i}$ 要么选 $b_{i}$ ，要最小化 $s u m$ 和 $n - s u m$ 的差。bitset 维护背包，只有 $O (n)$ 个本质不同物品，相同的物品二进制优化。复杂度 $O (\frac{n n}{w})$ 。

模拟赛 T4

找出最小生成树。从小到大加入边，维护边双，一定能去到一个边双的最小权值的边。并查集维护每个点属于哪个边双，维护边双最浅的点，维护 $1 \to u$ 的最小边权 $mn$ 和最小答案 $an s$ 。

对于 $(u, v)$ ，如果 $u, v$ 已经属于同个边双，不会贡献。如果 $(u, v)$ 是最小生成树中的边，如果 $1$ 能新到一些点，bfs 拓展，赋值答案。否则将 $u \to v$ 路径上的边双合并，设新边双最浅点为 $p$ ，将 $p$ 子树的所有点的 $mn$ 和 $an s$ 更新。如果更新到了非法的点，一定是没有被拓展到的，会在被拓展到时被覆盖。

8.19

CF622F

是 $k + 1$ 次多项式，算 $k + 2$ 个点值插值。维护阶乘， $\prod n - i$ ， $\prod (n - k - 2 + i)$ 。如果 $n - i$ 是奇数取负号。

arc165e

等价于每种情况出现的概率之和。概率为连通块相邻的点被选都在连通块被选之前，即 $\frac{i ! j !}{( i + j )!}$ 。设 $d p_{u, i, j}$ 表示根为 $u$ ，子树内选 $i$ 个点，有 $j$ 个相邻的点的连通块的概率， $O (n^{4})$ 转移。

abc249g

模拟赛 T3。

枚举 $\oplus x_{i}$ 和 $k$ 的最高相同的位 $i$ ， $i$ 位以下不用管。按位贪心确定 $\oplus y_{i}$ ，将 $2^{i} \frac{a}{2 ^{i}}$ 和 $2^{i} \frac{b}{2 ^{i}}$ 拼在一起放入线性基中。复杂度 $O (n lo g^{3} V)$ 。

减少有用的 $(a_{i}, b_{i})$ 。如果 $a_{i}$ 能被 $a_{1}, \dots, a_{i - 1}$ 表示出，那 $b_{i}$ 消去对应的 $b_{j}$ ，变成 $(0, b_{i}^{'})$ 不会造成影响。只有 $O (lo g V)$ 个 $(a_{i}, b_{i})$ 。复杂度 $O (n lo g V + lo g^{3} V)$ 。

8.20

模拟赛 T3

从深度大往小维护线段树，启发式合并。 $u$ 和 $v$ 处 $[l, r]$ 差分维护加 $1$ ，lca 对应 $u, v$ 的儿子处删除。每次修改后，线段树上二分极长非零连续段的左右端点，回答能回答的询问并删除询问。将询问挂在 $r$ 上，线段树维护区间 $l$ 的最大值，每次取出并删除。

CF1174E

$a_{1}$ 一定是 $2^{x} 3^{y}$ ，且 $y = 0/1$ 。每次 $x$ 或 $y$ 减一或不变，dp 即可。

8.21

CF1264D2

模拟赛 T2。

等于在唯一一个 $p r e_{i} = s u f_{i + 1}$ 的地方计算答案。枚举分界点，设左边有 $x$ 个 (， $l$ 个 ?，右边有 $y$ 个 )， $r$ 个 ?，答案为 $\sum_{i = 0}^{l} (i l) \times (x + i - y r) \times (x + i) = x \times \sum_{i = 0}^{l} (i l) \times (r - x + y - i r) + l \times \sum_{i = 0}^{l} (i - 1 l - 1) \times (r - x + y - i r) = x (r + y - x l + r) + l (r - x + y - 1 l + r - x)$ 。

CF1616H

模拟赛 T4。

建 trie dp，设 $f_{u}$ 表示 $u$ 子树内选点两两异或小于等于 $x$ 的方案数， $g_{u 1, u 2}$ 表示 $u 1, u 2$ 子树内选点两两异或小于等于 $x$ 的方案数。分讨向下递归，每个点只经过一次。

Explorer

2024.8 做题记录

8.1

8.3

8.6

8.7

8.8

8.9

8.10

8.11

思路

8.12

8.13

8.14

8.15

8.17

8.19

8.20

8.21

Graph View

Table of Contents

Backlinks