QBXT 2023 国庆集训 做题记录

Day 1

100 + 30 + 0 + 100．

A. 正方形

二维 ST 表弄个关于颜色的 bitset，然后就可以二分了．

B. 等差

诈骗题．一眼看到了一个不弱于快速阶乘算法的东西，然而模数够小，于是 $n$ 过大的时候就直接寄了．

$d = 1$ 是简单的，预处理阶乘及其逆元就可以做了．其他情况给每项除个 $d$ 就做完了．

C. npc 与 slime

即对 npc 创不死玩家的地图计数．注意到由于玩家左侧只会有 slime，且人类只能通过 slime 来刷级，所以 npc 能够创死在 $i$ 玩家当且仅当玩家右侧存在一个长度 $> s_i + i - 1$ 的 slime 连续段．

直接钦定 $i$ 个 slime 连续段和其后的 npc 然后容斥即可．注意讨论是否钦定 $n$ 号位置的 npc．

D. 矿泉水

注意到任何时刻序列单调不升，所以考虑维护轮廓线．

用 set 维护拐点即可．细节有点多．

当然也可以线段树！只是我傻逼了没想到．

Day 2

100 + 50 + 50 + 100．

A. 阶乘

考虑算出 $n!$ 的质因数分解．注意到 $a_i \le 2 \times 10^5$，故只用保留 $2 \times 10^5$ 内的质数即可．

然后给 $a$ 排序，从小到大贪心拿，正确性显然．拿的操作直接暴力做就好了，我也不知道为什么是对的．

B. 合并

典中典区间 DP，为啥写挂了呢．

设 $f_{l, r}$ 表示合并区间 $[l, r]$ 的最小代价，转移枚举区间断点，钦定断点到某个端点的距离是 $k - 1$ 的倍数．然后直接转移就能过了．

C. 填数

首先注意到对于互相包含的限制区间，大的那个没用，直接去掉．问题转化为对多个互不包含的区间限制计算方案数．

这个限制不漂亮，考虑计算对于所有的区间，内部都不存在相同数的序列数量．

把区间按照右端点升序排序，考虑设计一个 DP．设 $f_{i, j}$ 表示考虑了前 $i$ 个区间，钦定满足 $j$ 个区间限制的方案数．转移考虑枚举上一个区间：

1. 若相交，发现相交部分已经处理过，只需处理新增部分的方案数．
2. 若不相交，需乘上中间部分随便选的方案数．

然而这样时间复杂度是 $O(n^3)$ 的，无法通过本题．发现由于要容斥，事实上我们只关心 $j$ 的奇偶性，那么第二维只用记录 $0 / 1$ 即可．

D. 无向图

首先先二分，转化成对 $< \lambda$ 的边计数．

记录一个全集的值域线段树，再对每个点记录其邻接边的值域线段树．若查询的 $k$ 个点之间没有连边，直接差分就能计算答案．

若 $k$ 个点之间有边，发现会被多减去 $1$ 次，加回来即可．

Day 3

50 + 100 + 70 + 0．

A. mexor

乱搞一下就 50 分，再乱搞一下就过了．

不是很懂啊．

B. wbtree

不难发现和自己子树中最浅的没有匹配过的点匹配是最优的．线段树合并即可．

C. andgraph

考虑优化建图，对每一位建一个虚点，若 $a_i$ 的第 $j$ 位为 $1$，$i$ 往虚点 $j$ 连一条权为 $a_i$ 的边．容易发现最短路意义不变．

然而这样需要跑 $n$ 次最短路，寄了．考虑最短路一定形如 $u \to$ 虚点 $\to \cdots \to$ 虚点 $\to v$．考虑处理出两虚点之间的最短路，然后枚举 $u$ 和 $v$ 走哪个虚点．时间复杂度为 $O(n \log^2 n)$，已经可以通过本题．

预处理虚点 $\to v$ 这一部分后可以做到 $O(n \log n)$．好像还能更牛一点，但是不会了．

D. splitham

巨大恶心 DP．

注意到每次划分出的集合是确定的，故可以设 $f_{i, S, j}$ 表示正在走 $S$，从 $i$ 开始从 $j$ 结束的最短路．

转移枚举分割出的两部分 $P$ 和 $Q$ 的入点 $x$ 和出点 $y$，有

$$f_{i, S, j} = \min_{x, y} f_{i, P, x} + \operatorname{dist}(x, y) + f_{y, Q, j}$$

根据经典结论，这个状态数是 $O(n^2)$ 的．

然后预处理所有 $x$ 的 $\min\limits_y \operatorname{dist}(x, y) + f_{y, Q, j}$ 即可 $O(n^3)$ 转移．

Day 4

100 + 0 + 100 + 0．

A. 小葱买糖

对质因子根号分治，小于 $\sqrt{10^9}$ 的直接开桶计，大于 $\sqrt{10^9}$ 的至多 $n$ 个，开个数组记下来然后去重．最后乘起来．

B. 小葱拿糖

大搜索．不会．

C. 小葱吃糖

设 $d_i$ 表示原序列 $[1, i]$ 这段前缀形成的数，则一个区间 $[l, r]$ 可以被吃掉当且仅当 $d_r - d_{l - 1} 10^{r - l + 1} \equiv 0 \pmod p$．

整理一下式子，即对 $l \le x < y \le r$ 且满足 $d_x 10^{y - x} \equiv d_y \pmod p$ 的点对计数．

考虑分治．设当前分治区间为 $[l, r]$，对跨越分治中点 $m = \lfloor (l + r) / 2 \rfloor$ 的点对 $(x, y)$ 计数．由于跨过了分治中点，我们可以将式子写为 $d_x 10^{m - x} 10^{y - m} \equiv d_y \pmod p$．预处理 $f_i$ 表示 $[l, m]$ 中满足 $d_x 10^{m - x} = i$ 的 $x$ 数量和 $g_{i, j}$ 表示 $[m + 1, r]$ 中满足 $10^{y - m} = i$，$f_y = j$ 的 $y$ 的个数，然后枚举 $i = d_x 10^{m - x}$ 和 $j = 10^{y - m}$，跨中点的点对数目就是 $\sum_i \sum_j f_i \times g_{j, ij}$．

此时不带修的问题已经可以通过离线询问后一遍分治解决，考虑带修，发现分治过程中维护的信息数量是 $\Theta(p^2)$ 的，可以直接丢上线段树．

时间复杂度 $\Theta(n p^2 \log n)$．

D. 小葱卖糖

大 DP，不会．

Day 6

100 + 100 + 10 + 0．

A. 修改

并查集搞搞就做完了．

B. 染色

显然对于形态相同的树，方案数是一样的．

考虑设 $f_S$ 表示形态为 $S$ 的树染色的方案数．转移枚举 $S$ 的根节点的子树的形态，根节点可以随便填，先给方案乘上 $m$，然后不同形态的子树方案独立，乘起来即可．

考虑计算所有形态为 $S^\prime$ 的子树染色的方案数，设这种子树的个数为 $\mathrm{ct}$，那么就相当于将 $\mathrm{ct}$ 个相同的小球放入 $f_{S^\prime}$ 个不同的盒子中，插板法可得方案数为 $\binom{\mathrm{ct} + f_{S^\prime} - 1}{f_{S^\prime} - 1}$．

那么对于形态为 $S$ 的树，枚举以其根节点的某个儿子为根的子树的形态 $S^\prime$，设这样的子树有 $\operatorname{ct}(S^\prime)$ 个，有转移：

$$f_S = m \prod_{S^\prime} \binom{\operatorname{ct}(S^\prime) + f_{S^\prime} - 1}{f_{S^\prime} - 1}$$

注意到这个组合数不能直接算，但是其等于 $\binom{\mathrm{ct} + f_{S^\prime} - 1}{\mathrm{ct}}$，由于 $\sum \mathrm{ct} = O(n)$，所以可以直接暴力递推．

如何记录形态到状态里？树哈希或者 std::map<std::multiset<int>, int> 映射．

C. 棋盘

A334551．

容易发现一个 $2 \times 2$ 的格子里只能放一个棋子．那么将其缩起来，问题转化为 $n \times n$ 个格子，每个格子的放置状态有 $4$ 种，然后互不影响的方案数．不妨记每种格子的 $4$ 种状态为 ABCD，如图：

对于横着的两个格子，若右边的确定为 A，则左边的也要是 A，但确定左边时右边有多种可能．BCD 的情况类似．于是我们可以得到，最终的填入方案一定形如下图：

那么枚举折线的起止点，方案数为：

$$\sum_{0 < a < n} \sum_{0 < b < n} \sum_{a \le c < n} \sum_{b \le d < n} \binom{c - a + d - b}{c - a} + 2\sum_{i < n} \sum_{j < n} \binom{i + j}{i} + \binom{2n}{n}$$

又由于矩阵可以旋转 $90$ 度，设上式和为 $s$，答案是 $2s - (n + 1)^2$．

稍微推推就能得到答案为

$$8\binom{2n}{n} - 3(n + 1)^2 + 4(n + 1) - 8$$

D. 神奇的函数

大构造．不会．

Day 5

100 + 100 + 0 + 0．

A. 奇怪的等式

发现题目中的那个诡异操作就是将 $a_i, a_j, a_k$ 的 $2$ 进制表达拼起来再转回 $10$ 进制，于是枚举 $j$ 和 $a_j$ 拼在 $P$ 中的位置，这样 $a_i$ 和 $a_k$ 的值都是确定的，拿个桶统计．

B. 机器人

发现撤销某个操作会导致一段后缀的点发生平移，于是枚举删的是哪个操作，倒着扣一遍贡献，过程中记录答案即可．

C. 装饰品

神仙．

如果我们确定了第 $i$ 个物品在最终的方案中的选取次数 $c_i$，方案数由下式给出

$$\binom{n}{c_1, c_2, \cdots, c_k} = \binom{n}{c_1} \binom{n - c_1}{c_2} \binom{n - c_1 - c_2}{c_3} \cdots \binom{n - c_1 - c_2 - \cdots - c_{k - 1}}{c_k}$$

考虑这个东西 $\bmod\ 2$ 的结果，若 $\not= 0$，那么右边的每一个组合数都 $\not= 0$．

回忆 Lucas 定理，$\binom{n}{m} \bmod 2 \not= 0$ 的充要条件为：令 $s(n)$ 表示 $n$ 的二进制表达中为 $1$ 的那些位的下标构成的集合，$s(m) \subseteq s(n)$．

若上式 $\not= 0$，逐个考察组合数，对于 $\binom{n}{c_1}$，有 $s(c_1) \subseteq s(n)$，此时可以得出 $n - c_1$ 没有退位；对于 $\binom{n - c_1}{c_2}$，有 $s(c_2) \subseteq s(n - c_1)$，此时可以得出 $n - c_1 - c_2$ 也没有退位．归纳一下，我们可以得出：

1. $\bigcup\limits_{i = 1}^k s(c_i) = s(n)$．
2. $\forall i \not= j, s(c_i) \cap s(c_j) = \varnothing$．

即对于所有 $i$，$s(c_i)$ 构成了对 $s(n)$ 的一个划分．

那么我们可以从低到高考虑对于 $n$ 的每一个为 $1$ 的位，该位被哪一个 $c_i$ 包含．我们记录当前和为 $S$ 的方案，由于之前的位已经确定，和 $m$ 之前的位不同的方案显然不用考虑，可以直接抛弃掉已经考虑过的位，故 $S$ 的数量是 $O(a_k)$ 的，可以使用 std::bitset 记录，时间复杂度 $O(kV \log n / w)$，其中 $V = \max a_i$，$w$ 为字长．

D. 最大带权独立集

太厉害了，不会做．

Day 7

A. 矩阵乘法

考虑这个东西的含义，发现就是最大化有 $n$ 个点的有向图的边数，使得图中不存在长度超过 $k$ 的路径．

可以考虑一个简单的构造，就是将 $n$ 个点划分成 $k$ 个部分，每个部分向其后的所有部分连边．这实际上是对 $T_{n, k}$ 进行了一个定向，其中 $T_{n, k}$ 是一个有 $n$ 个点的特殊的完全 $k$ 分图，其中每部点数差不超过 $1$，我们称其为 Turán 图，而根据 Turán 定理，这个图的边数是

$$\binom{n - m}{2} + (k - 1)\binom{m + 1}{2}$$

其中 $m = \lfloor n / k \rfloor$．

为啥这么构造就能达到上界呢，不懂．

B. 树

换根倍增．

C. 魔法城堡

分层图最短路即可．层和层之间可以使用 DP 转移，但貌似直接转移也不会寄？

D. GCD

$\Huge \red{\text{没写代码．}}$

首先计算 $f_n$ 显然可以矩阵快速幂．打表可以猜测 $f$ 的相邻两项绝对值要么相等要么互质．

考虑计算 $\gcd(a_1 f_n + a_2 f_{n + 1}, b_1 f_n + b_2 f_{n + 1})$，可以先跑一遍辗转相除消掉 $b_2$，然后转化为计算 $\gcd({a_1}^\prime f_n + {a_2}^\prime f_{n + 1}, {b_1}^\prime f_n)$．

但是目前计算两边的真实值仍然是不可接受的，考虑继续减小值的规模．若我们计算出了 $g = \gcd({a_1}^\prime f_n + {a_2}^\prime f_{n + 1}, f_n) = \gcd({a_2}^\prime, f_n) \le 400$，那么有 $\gcd({a_1}^\prime f_n + {a_2}^\prime f_{n + 1}, {b_1}^\prime f_n) = \gcd({a_1}^\prime f_n + {a_2}^\prime f_{n + 1}, {b_1}^\prime g)$，这个真实值的范围就可以接受了．