补题地址：https://zjusummer.contest.codeforces.com/

• ZJU-ICPC Summer 2020 Contest 1 by Group A
• * Problem A. MUG
• * Problem B. Count Angles
• * Problem F. Balloons Tower Defence
• ZJU-ICPC Summer 2020 Contest 2 by Group B
• * Problem A. The Number of Good Intervals
• * Problem D. Pick Branches
• ZJU-ICPC Summer 2020 Contest 3 by Group C
• * Problem A. FibTree
• * Problem C. More and more
• * Problem E. Election
• ZJU-ICPC Summer 2020 Contest 4 by Group A
• * Problem C. guofuqian50
• * Problem E. Problem of Card Bonus
• * Problem F. Magical String
• ZJU-ICPC Summer 2020 Contest 5 by Group B
• * Problem D. Cities
• * Problem F. Contour
• [absent]ZJU-ICPC Summer 2020 Contest 6 by Group C
• ZJU-ICPC Summer 2020 Contest 7 by Group A
• * Problem B. Card Game
• * Problem D. Cafeterias
• * Problem E. Lifelong Learning
• ZJU-ICPC Summer 2020 Contest 8 by Group B
• * Problem C. Thresholding
• * Problem D. Mysterious Machine
• * Problem E. Magic
• * Problem F. Can you find B
• ZJU-ICPC Summer 2020 Contest 9 by Group C
• * Problem A. An easy problem
• * Problem B. Ball
• * Problem F. FFT

Date:2020/7/13

Problem A. MUG

哇这个题面真的长不翻了QAQ

https://s1.ax1x.com/2020/07/16/U0LBo8.png

https://s1.ax1x.com/2020/07/16/U0LrFS.png

动态规划。设 \(f(i, 0/1/2)\) 表示按到第 \(i\) 个键时，当前键不按，左手按或右手按，产出的最大分数为多少。

由题意得状态转移方程：

• \(f(i, 0) = \max\{ f(i - 1, 0), f(i - 1, 1), f(i - 1, 2) \}\)
• \(t_i > t_{i - 1} \rightarrow f(i, 1) = \max\{ f(i - 1, 0) + s_i, f(i - 1, 2) +s_i\times \dfrac{ p_1}{100} \}\)
• \(t_i \le t_{i - 1} \rightarrow f(i, 1) = \max\{ f(i - 1, 0) + s_i, f(i - 1, 2) +s_i \}\)
• \(t_i < t_{i - 1} \rightarrow f(i, 2) = \max\{ f(i - 1, 0) + s_i, f(i -1, 1)+s_i\times\dfrac{p_2}{100}, f(i - 1, 2)+s_1\times\dfrac{p_3}{100}\}\)
• \(t_i \ge t_{i - 1} \rightarrow f(i, 2) = \max\{ f(i - 1, 0) + s_i, f(i -1, 1)+s_i, f(i - 1, 2)+s_1\times\dfrac{p_3}{100}\}\)

复杂度为线性。

Problem B. Count Angles

求平面中 \(n(\le 10^9)\) 条直线可以构成同旁内角对数的最大值，对 \((10^9 + 7)\) 取模，\(T(\le 10^5)\) 组数据。

显然当 3 条直线构成 3 个不重合的交点时同旁内角数最大为 6。

于是当 \(n\) 条直线不出现三线共点的情况是答案最大为 \(C_n ^3 \times 6 = n(n-1)(n-2)\)。

Problem F. Balloons Tower Defence

给定平面上 \(n(\le 10^5)\) 个点，判断是否存在一条直线，使该直线上有 \(n\times p\%\) 个点\((p\in[20, 100])\)。

考虑随机化算法：每次随机选取两个点，判断其构成的直线上的点的个数是否满足要求。

用 clock() 函数控制尝试次数，最后实在找不到了就跳出。

不难算出这样的误判率极低，因为 \(p\) 被保证不太小。

Date:2020/7/14

Problem A. The Number of Good Intervals

给定一个长度为 \(n(\le 4\times 10^6)\) 的数列 \(\{a_1, a_2, \cdots, a_n\}(a_i\le 4\times 10^4)\)，再给定 \(m(\le 2\times 10^5)\) 个询问，每次询问给出一个正整数 \(b(\le 4\times 10^4)\)，求有多少个区间 \([l, r]\)，满足 \(\gcd\limits_{l\le i\le r} \{a_i\} = b\)。

当一个正整数 \(x\) 与另一个数 \(y\) 取 \(\gcd\) 时，即 \(x \leftarrow \gcd(x, y)\)，若 \(x\) 较之前发生了变化，那么一定是减小了至少两倍。那么 \(x\) 最多改变 \(\log x\) 次，\(n\) 个就是 \(n\log x\) 种值。

于是可以用 map 直接做，每做到一个数 \(a_i\)，就将上一轮的 map 中的元素结合 \(a_i\) 更新至该轮 map 中，然后倒入答案 map。时间复杂度 \(O(n\log^2 x + m)\)，\(x\) 为值域。

遗憾的是 st 表做法因为时空两爆炸被卡了。 /dk

Problem D. Pick Branches

\(n\times n\)棋盘上的 \((n + 1)^2\) 个点，从 \((0,0)\) 出发的直线，恰好通过 \(m\) 个点的方案数。\((1\le n, m\le 5\times 10^6)\) 定义两个方案是不同的，当且仅当存在一个点属于方案 A 不属于方案 B。\(T(\le 10^5)\) 组数据。

若我们的直线为 \(y = \dfrac{a}{b} x(a < b，\gcd(a, b))\)，那么上面的点数为 \(\lfloor{\dfrac{n}{a}}\rfloor + 1\)。

于是答案不难表示为：\(\sum\limits_{i = 2}^n \sum\limits_{j = 1}^{i} [\gcd(i, j) = 1][\lfloor{\dfrac{n}{i}}\rfloor + 1 = m]\)。

把其中的互质换成 \(\varphi\)，可得 \(\sum\limits_{i = 2}^n \varphi(i) [\lfloor{\dfrac{n}{i}}\rfloor + 1 = m]\)。

可以看出后面的条件实质上是连续的一段区间，于是预处理出 \(\varphi\) 及其前缀和即可。使用线性筛可以有 \(O(n + T)\) 的复杂度。然而这里并没有用

Date:2020/7/15

Problem A. FibTree

给定一个 \(n(\le 10^5)\) 个点，\(m(\le 10^6)\) 条边的无向图，边权 \(c\in \{0, 1\}\)。求问是否存在一个生成树，其边权和在斐波那契数列中出现过。

当我们得到一个生成树后，我们可以通过把一条 1 边用 0 边替换，或用 1 边替换 0，这样可以使总边权 +1 / -1。

那么我们只需要用 Kruskal 求出最大、最小生成树，然后判断整个区间中是否存在斐波那契数即可。复杂度 \(O(m\log m)\)。

Problem C. More and more

给定一个长为 \(n(\le 3\times 10^5)\) 的数列 \(\{a_1, a_2, \cdots, a_n\}(a_i\in [-10^5, 10^5])\)，现在可以选取 不超过 \(m(\le 30)\) 个 互不相交 的区间，对选中的区间中每个数字 \(a_i\) 乘上 \(x(\in [-10^4, 10^4])\)。最后对操作后的序列求最大子段和，试问可以得到的最终结果的最大值。

动态规划。设：

• \(f(i, j)\) 表示，选到第 \(i\) 个数时，且 \(a_i\) 处于被选中区间中，加上当前的区间一共选中了 \(j\) 个区间的答案。
• \(g(i, j)\) 表示，选到第 \(i\) 个数时，且 \(a_i\) 不处于被选中区间中，之前一共选中了 \(j\) 个区间的答案。

那么根据定义，可得状态转移方程：

• \(f(i, j) = \max\{ f(i - 1, j), g(i - 1, j - 1), 0 \} + a_i \times x\)。
• \(g(i, j) = \max\{ f(i - 1, j), g(i - 1, j), 0 \} + a_i\)。

最后整个数组的最大值即为答案。时间复杂度 \(O(nm)\)。不开 long long 见祖宗

Problem E. Election

给定一个 \(n(\le 3\times 10^5)\) 个结点的树，带边权 \((a_i < 2^{31})\)，若为以结点 \(i\) 为根，那么一个结点 \(j\) 产生的价值为 \(\sum\limits_{k \in \text{path}(j \rightarrow i)} [a_k < a_j]\)。记一个结点 \(x\) 作为根结点时产生所有结点的价值和为 \(f(x)\)，试求 \(\sum\limits_{x\in \text{V}} f(x)\)。（\(\text{V}\) 表示点集）

线段树合并。当处理到结点 \(x\) 时，那么我们计算 \(x\) 的贡献：

• 对于 \(x\) 的某一子结点 \(y\)，对答案产生 不在子树 \(y\) 中的结点数 \(\times\) 子树 \(y\) 中权值严格小于 \(a_x\) 的结点数。
• 子树 \(x\) 中的结点数 \(\times\) 不在子树 \(x\) 中的，权值严格小于 \(a_x\) 的结点数。

维护子树中点权的集合，可以用动态开点权值线段树维护，并在递归中往上合并。

时空复杂度 \(O(n\log n)\)。

Problem C. guofuqian50

[10s/512MB] 给定一个 \(n(\le 5\times 10^4)\) 个点，\(m(\le 10^5)\) 条边的无向图，带边权 \((\le 10^9)\)。上面标有 \(k(\le n)\) 个特殊点，记特殊点集为 \(S\)。每个点有一个权值 \(w_i(\le 20)\)。定义一个点 \(u\) 在能见度为 \(r\) 的时间内的“危险度”为 \(\sum_{v\in S}[\text{dist}(u, v)\le r]\)（\(\text{dist}(u, v)\) 表示 \(u, v\) 两点之间的最短距离），若其危险度大于 \(\ge w_u\) 则称点 \(u\) 为“危险的”。现在有 \(t(\le 10^5)\) 天，第 \(i\) 天的你能见度为 \(r_i(\le 10^{18})\)，求每个点在这 \(t\) 天中，成为“危险的”的天数。

本质上就是求距离每个点前 \(w_i\) 近的点与之的最短距离的集合。只要得到了这个，那么我们看看第 \(w_i\) 近的点的最短距离是否超过 \(r_i\) 即可。

之所以可以这么考虑，是因为 \(w_i\) 的范围非常小，使之成为了本题的突破口。

这可以魔改一下 Dijkstra 算法实现，但还是很多细节的，比如如果直接将所有特殊点放进去跑，会出现“串味”的现象，导致反复横跳。

要避免这个，我们还应保存一个 源点编号，然后将原来保存答案的数组换成 map 或 unordered_map，记录不同源点的答案。

但记录全部仍然无法满足要求，于是我们回顾 \(w_i\le 20\) 这个条件，根据 Dijkstra 贪心的思想，先到的一定更优，于是我们限定 map 的大小最大为 \(\max \{ w_i\}\)，超出了直接跳过。

这样的时间复杂度为 \(O(w(n+m)\log m)\)。

Problem E. Problem of Card Bonus

给定三个长为 \(n(\le 10^3)\) 的数组 \(a_{1\cdots n}(\le 10^4), b_{1\cdots n}(\le 10^4), c_{1\cdots n}(\le 2\times 10^6)\)。给定 \(p(\le 10^4)\)，求一组 \(x_{1\cdots n}(\in \{0, 1\})\)，满足 \(\sum\limits_{1\le i\le n} a_i x_i \le p \le \sum\limits_{1\le i\le n} b_i x_i\) 时，\(\sum\limits_{1\le i\le n} c_i x_i\) 的最小值。

动态规划。设 \(f(i, j)\) 为前 \(i\) 个 \(x\)，满足 \(\sum a_i x_i \le p \le \sum b_i x_i\) 时 \(\sum c_i x_i\) 的最小值。

那么对于当前状态，有两种转移：

• \(x_i = 0\to f(i - 1, j)\) 不选。
• \(x_i = 1\to\) 所有于 \(j\) 的差值在范围 \([a_i, b_i]\) 的 \(k\)， \(f(i - 1, k)\) 的最小值。由于当前被选择，需要加上 \(c_i\)。

状态转移方程：

\[f(i, j) = \min( f(i - 1, j), \min\limits_{j - b_i \le k \le j - a_i} \{ f(i - 1, k) \} + c_i )
\]

但直接做显然是 \(O(n\times p^2)\) 的。由于我们发现，方程中的第二项本质上是一个滑动最值问题，考虑用单调队列优化这个过程。

如果卡空间还可以把第一维滚掉，但是这里不需要。时间复杂度 \(O(n\times p)\)。

Problem F. Magical String

给定一个一个文本串 \(A(|A| \le 500)\)，以及一个大小为 \(m\) 的模式串集 \(B = \{B_1, B_2, \cdots, B_m\}(m\le 10^5, |B_i| \le |A|, \sum|B_i| \le 10^6)\)。试选出一个 \(B\) 的子集 \(S\)，满足 \(S\) 中的字符串存在一种排列方式（可以任意排列），使排列后的新字符串 \(C\) 无限向两端复制的结果等价于 \(A\) 向两端无限复制的结果。求 \(\min |S|\)。

非常显然，若 \(S\) 可以匹配到 \(A\) 的一个循环节，那么整个都可以匹配。而 \(A\) 的一个循环节无限复制的结果和 \(A\) 本身复制的结果是相同的。于是我们之间匹配 \(A\) 的 最小循环节 即可。记这个最小循环节长度为 \(L\)。

我们处理出 \(B\) 中的模式串在 \(A\) 中的出现情况。对于 \(A\) 的某一个位置 \(i\)，若 \(A[i, j]\) 是 \(B\) 中的一个串，那么我们称 第 \(i\) 个位置可以转移到第 \(j+ 1\) 个位置。但可能会超出最小循环节，于是令 \(j\) 对 \(L\) 取模。

考虑如何对于所有的 \(i \in [1, L]\)，处理出所有从 \(i\) 开始的转移。由于转移中的 \(B\) 一定是 \(A[i, |A|]\) 的 一个前缀，当一个位置断掉了，之后一定不会匹配。可以用 Trie 树辅助实现这一过程。

现在我们已经得到了所有转移，那么我们不妨 将位置视为点，将转移视为边，构成了一个有向图。 其中每使用一次转移，就相当于使用 \(B\) 中 的一个元素。这个元素并不会重用，因为处理出了 \(A\) 的最小循环节。

那么我们要求的答案就是 最小环的大小。这个直接 Floyd 可以过，复杂度 \(O(n^3)\)。

思路主要来自 kqh （orz）

Problem D. Cities

给定一个 \(n(\le 50)\) 个点，\(m(\le 110)\) 条边的无向图，起始点位于顶点 \(1\)，在一天的时间内有三种选择：往相邻点走，停留在原地，或结束。给定 \(t(\le 10^8)\)，求在 \(t\) 天内有几种不同的行动方案数 \(\pmod{2020}\)。

考虑到 \(n\) 非常小，那么可能提示我们用邻接矩阵存图。当一个邻接矩阵 \(A_{i, j}\) 可以表示结点 \(i, j\) 的联通状态，但这里我们理解为 从结点 \(i\) 到结点 \(j\) 的行动方案数。因此我们令所有 \(\in[1, n]\) 的 \(i\)，\(A_{i, i} \leftarrow 1\)。

若我们设一次（一天）转移后得到矩阵 \(B\)，不难得出：

\[B_{i, j} = \sum\limits_{k = 1}^n A_{i, k}\times A_{k, j}
\]

这个一看就是 矩阵乘法，于是我们记一次转移的结果为 \(A^2\)，那么 \(t\) 次即为 \(A^t\)。然而不幸的是，矩阵 \(A^t\) 中的元素之和并不是我们的答案，因为可以任意的退出。很显然只要把所有 \([0, t]\) 的矩阵幂算出来，于是答案其实是：\(C = R\times \sum\limits_{p\in[0, t]} A^p\)，其中 \(R_{1, 1} = 1\)，其余元素为零。

但这东西仍然无法直接求。我们又设 \(S = \begin{bmatrix} A & 0 \\ I & I\end{bmatrix}\)，那么算出 \(S^{t+1}\) 即可，\(C = (S^{t+1})_{1, 2}\)。关于矩阵套矩阵：POJ 3233 - Matrix Power Series

时间复杂度 \(O(n^3 \log t)\)

Problem F. Contour

平面上有 \(n(\in [4, 10^4])\) 个点，现在要用这 \(n\) 个点构造一个图形，满足：

• 这个图形是闭合的；
• 每条边的端点必须是给定的点，且每个给定的点必须被用到；
• 每个点连接的两条边必须互相垂直；
• 每条边必须平行于坐标轴；
• 任意两条边除了顶点外不能相交；
• 这个图形的周长最小。

如果有解，输出最小周长，否则输出\(0\)。

构造题。对于部分 \(x\) 坐标相同的点的点集 \(S\)，若要使有解，必须满足 \(|S|\bmod 2 = 0\)。对于 \(y\) 坐标同理。根据这个思想，我们可以得出一个规律——对于在同一竖直线或水平线上的点，应该是第一个和第二个，第三个和第四个……第 \(2k-1\) 个和第 \(2k(k\in \mathbb{Z})\) 个连边。

因此不难得出以下构造算法：先将所有点分别按 \(x, y\) 为第一关键字，第二关键字排序，依据上述结论连上所有竖直的线段。题目要求连通，于是考虑使用并查集；题目又要求线段不相交，于是存下所有竖直的线段。再将所有点分别按 \(y, x\) 为第一关键字，第二关键字排序，依据上述结论连上所有水平的线段。并更新并查集，判断相交情况。

最后若全图连同则有解，输出答案。该解唯一，因为只能这样构造，不存在调整之后得到另一个解的情况。于是自然就是最优解了。

Problem B. Card Game

你正在与 \(p(\le 10^5)\)（包括自己）个人玩一个游戏，每个人手上有一张手牌，手牌上有数字 \(b_1, b_2, \cdots b_n(\in[1, c(\le 10^5)])\)。牌堆大小为 \(n\)，其上的数字 \(\in[1, c]\)。每个人轮流将桌上的一张卡片换成自己手上的卡片，你是第一个操作的。如果最后的桌子上留下的卡片中 \(h(\in [1, c])\) 是 唯一 的众数那么视为你成功。求有多少种可行的操作使你必胜，并输出必胜策略中交换的牌。

我们不妨从最坏情况考虑——每个人都不希望你赢，于是纷纷把你的牌 \(h\) 换掉。

因此我们令自己 最后操作。枚举一遍牌堆的牌并验证。维护全局众数可以直接线段树。

时间复杂度 \(O(n\log c)\)。注意 \(n = 1\) 时特判，具体见代码。

Problem D. Cafeterias

给定一个 \(n(\le 10^5)\) 个点， \(m(\le 2 \times 10^5)\) 条边的无向图，并标有 \(k(\le n)\) 个特殊点。现给定 \(T(\le 10^5)\) 个询问，每次给出整数 \(t(\le 10^9)\)，求有多少点存在到达特殊点，长度为 \(t-1\) 的 不一定 简单的路径。

显然一跳路径可以通过“反复横跳”来加长路径：\(1 \to 3 \to 4\) 可以变为 \(1\to 3 \to 4\to 3\to 4\)。而且一次增加 \(2\)。

于是求出两种最短路——长度分别为奇数和偶数时的最短路径长。求出最短路可以通过“反复横跳”来构造出新的路径。由于图不带边权，于是直接 Bfs。

然后将所有最短距离排序（无法到达记为无限大）。

对于询问的 \(t\)，我们先判断其奇偶性，再在最短路长数组上二分即可。

时间复杂度 \(O(n\log n)\)。

Problem E. Lifelong Learning

给定一个长为 \(n(\le 10^6)\) 的数列 \(\{a_1, a_2, \cdots, a_n\}(a_i \le 10^6)\)。每次操作可以改变数列中的一个元素的值。求最少的操作次数，使最终的数列满足：前半部分满足 \(a_i + 1 = a_{i + 1}\)，后半部分满足 \(a_i - 1 = a_{i + 1}\)。若 \(n\) 为偶数则 \(a_{\frac n 2} = a_{\frac n 2+1}\) 。

我们先将每一个数，以中间数 \(\text{mid} = \lfloor \dfrac{n+1}{2} \rfloor\) 为基准，对于每一个位置 \(i\)，进行操作 \(a_i \leftarrow a_i + |i - \text{mid}|\)。

接下来我们在操作后的 \(a\) 数列上贪心地取众数，记众数的出现次数为 \(k\)。显然这样可以最大化不改的数的个数。

答案即为 \(n - k\)。

Problem C. Thresholding

给定一个 \(w(\le 640)\times h(\le 640)\) 的矩阵，矩阵中的元素为整数且 \(\in [0, 2^{16})\)。你可以设一个间值 \(k\)，将矩阵中所有 \(\le k\) 的元素归入集合 \(0\)，其他的归入集合 \(1\)。设集合 \(S\) 占总数大小的比例为 \(\omega_S\)，集合 \(S\) 的方差为 \(\sigma_S^2\)。求 \(\sigma_w^2 = \omega_0\sigma_0^2 + \omega_1\sigma_1^2\) 的最小值。

注意到本题中的“矩阵”是假象，实质上就是一堆数字。

于是显然可以枚举数字的分布情况，这可以通过排序完成。枚举时需要动态维护左右两部分的方差，可以使用公式 \(\sigma = \sum x^2 - (\sum x)^2\)。预处理一个前缀和以及前缀

但理论上不能直接扫，因为我们不能让两个相同的元素在不同的集合里，于是这里要特判。然而好像不判也过了。

复杂度 \(O(wh\log (wh))\)。直接三分应该也行。

Problem D. Mysterious Machine

给定三个正整数 \(x, y, z(\le 5\times 10^3)\)。构造三个 01 串 \(A, B, C\)，满足 \(\text{LCS}(A, B) = x, \text{LCS}(B, C) = y, \text{LCS}(A, C) = z\)。其中 \(\text{LCS}(S, T)\) 表示字符串 \(S, T\) 的最长公共子序列长度。构造出的长度不超过 \(10^4\)。

构造题。我们钦定 \(x \le y \le z\)，那么我们先将在字符串 \(A\) 中填充 \(z\) 个 \(\texttt 1\)，在 \(B\) 中填充 \(x\) 个 \(\texttt 1\)。这样保证了 \(\text{LCS}(A, B) = x\)。

然后再向 \(B\) 后面添加 \(y - x\) 个 \(\texttt 0\)，最后在 \(C\) 中加 \(5000\) 个 \(\texttt 1\)，\(5000\) 个 \(\texttt 0\)。这样显然满足题意，因为我们可以近似的认为 \(\text{LCS}(B, C) = |B| = y, \text{LCS}(A, C) = |A| = z\)。

Problem E. Magic

给定 \(n(\le 20)\) 个字符串 \(S_1, S_2, \cdots , S_n(\sum|S_i| \le 10^5)\)，任意排列这些字符串并拼接，可以计算出得到的新串的 本质不同 的子序列的个数，空串也算。求有多少种排列的方式，使得得到的新串的本质不同的子序列的个数为偶数。字符集 \(\Sigma\) 为全体小写英文字母。

若只计算单串 \(S\) 的本质不同的子序列的个数，我们可以设计一个动态规划算法：设 \(f(i, c)\) 为子串 \(S[1, i]\) 以字符 \(c\) 结尾的本质不同的子序列的个数，且令 \(s(i) = \sum\limits_{c\in \Sigma} f(i, c)\)，即当前的答案。那么有状态转移方程：

\[f(i, c) = \begin{cases}
f(i - 1, c) & c \ne s[i] \\
s(i-1) & c = s[i]
\end{cases}
\\
s(i) = 2s(i-1) - f(i, s[i])
\]

由于本题只与奇偶性有关，我们不妨对 \(2\) 取模：

\[s(i) = (2s(i - 1) - f(i, s[i]))\bmod 2 = f(i, s[i])
\]

这相当于 \(f\) 与 \(s\) 之间的 交换。

---

我们注意以下初始状态：\(f = 0\)，只有 \(s(0) = 1\)（空串也算），而上式只存在交换，因此不难断定 为 1 的字符位置只有一个。

那么我们只需抓住这个位置即可。我们使用上述思想预处理出 \(t\)（代码中为 \(f\) 数组） —— \(t(S, c)\) 表示 1 的位置为 \(c\) 开始，“通过”在字符串 \(S\) 后 1 的位置。

---

根据这个 1 的位置，我们再考虑一种 dp：设 \(g(S, c)\) 表示，字符串集合（编号） \(S\) 中的字符串任意拼接，当 1 的位置为字符 \(c\) 时，存在几种满足题意的方案。

那么对于每一个状态 \(g(S, c)\)，有：

\[g(S \cup \{i\}, t(i, c)) \leftarrow g(S \cup \{i\}, t(i, c)) + g(S, c)
\]

显然需要满足条件 \(i \not \in S\)。

状态压缩一下，可以有 \(O(2^n \times n|\Sigma|)\)。

F. Can you find B

给定长度为 \(n(\le 100)\) 的数列 \(\{a_1, a_2, \cdots , a_n\}(a_i \le 50)\)。试构造出数列 \({b}\) ，使 \(\sum\limits_{i = 1} ^n |a_i - b_i|\) 最小且 \(\{b\}\) 中的任意两个元素 \(a, b\) 满足 \(\gcd(x, y) = 1\)。求出这个最小值。

\(\gcd = 1\) 的条件是比较苛刻的，这导致了 \(\{b\}\) 中会存在大量的 \(1\)。

又因为 \(a_i \le 50\)，所以 \(b_i \le 100\)，原因是选择超过 \(100\) 的数显然不如直接选 \(1\)。

于是我们有这样一个 dp：设 \(f(i, S)\) 表示对于 \(a\) 的前 \(i\) 个数，选定数的 质因子 集合为 \(S\)，得到 \(a, b\) 的最小总差值。

那么有转移方程：

\[f(i, S) = \min_{\text{div}(j) \not\subseteq T } \{ f(i-1, T\cup \text{div}(j)) + |a_i - j| \}
\]

然而直接状压计算量高达 \(2^{25} \cdot 100 \cdot n\)，原地爆炸。因为 \([1, 100]\) 内的质数有 \(25\) 个。

---

我们又发现一个性质：对于一个 \(>50\) 的质数，我们只可能选择其本身而非其倍数。原因见上，显然。

于是我们只枚举 \(50\) 以内的质数即可——范围缩小至 \(15\) 个。对于 \(a\) 数列，我们贪心地将其从小到大排序，小的对应小的。

我们计算答案时，我们取 左半部分的 dp，右半部分的较大质数。

dp 仍然是那个 dp，复杂的直降至 \(O(2^p \times n \times \max \{a\})\)，其中 \(p = 15\)。

Problem A. An easy problem

给定 \(n(\le 10)\) 个互不相同数字 \((\in[0, 9])\)。选择若干个数字拼接成整数 \(a\)，剩下拼成整数 \(b\)，拼成的数不应含前导零。求 \(\min |a - b|\)。

真·签到。\(n\) 很小，可以暴力枚举 next_permutation。

但是有一个技巧——要最小化差值，一定是从中间分割数列。

一个小优化：\(n=10\) 时答案固定，直接输出。

Problem B. Ball

给定两个球体，坐标大小，半径 \(\le 10^2\)，求两个球体的体积并。

计算几何，分类讨论。

• 不相交，答案为 \(V_1 + V_2\)。
• 包含，答案为 \(\max(V_1, V_2)\)。
• 否则，答案为 \((V_1 + V_2) - (r_1 + r_2 - d)^2\pi \times (d^2 + 2d(r_1 + r_2) - 3(r_1^2 + r_2^2) + 6r_1r_2)/(12d)\)，其中 \(r_1, r_2\) 为两圆半径，\(d\) 为两圆心距离。

Problem F. FFT

给定 \(n(\le 10^2)\) 个（有标号的）点，你可以在其间任意连边使之成为连通图。现在限定只允许连 \(m\) 条边，试问连成连通图的方案数。你需要根据所有的 \(m \in [0, \frac{n(n - 1)}{2}]\) 输出答案。

本题实质上是 限定边数有标号连通图计数 问题。

以下用 \(c(x)\) 表示 \(\frac{x(x - 1)}{2}\)。

考虑一种 dp：设 \(F(m, k)\) 为通过 \(m\) 条边连出 \(k\) 个连通块的方案数，\(G(m, k)\) 表示通过 \(m\) 条边，连成 \(k\) 个“假块”（人为划分的块，块间可能有连边）的方案数。

那么我们可以用 \(F\) 来表示 \(G\)：

\[G(m, k) = \sum\limits_{j = k}^{n} F(m, j) \begin{Bmatrix} j \\ k \end{Bmatrix}
\]

我们可以选择个数大于等于 \(k\) 的块数进行“合并”，其中 \(\begin{Bmatrix} j \\ k \end{Bmatrix}\) 表示 \(j\) 个连通块并入 \(k\) 个“假块”的方案数，即 第二类斯特林数。

但如果要反过来用 \(G\) 表示 \(F\) 呢？于是我们使用 斯特林反演 点击学习

\[F(m, k) = \sum\limits_{j=k}^n G(m, j)\begin{bmatrix}j\\k\end{bmatrix}(-1)^{j-k}
\]

方案数那么答案就是当 \(k = 1\) 时，代入得 \(\sum\limits_{j=1}^n G(m, j)(j-1)!(-1)^{j-1}\) 即为所求。

---

但我们发现这个直接求居然比暴力 \(O(n^6)\) 还慢。于是我们把这个 \(G\) 拆成 \(H\)——\(H(i, j, m)\) 表示选取 \(i\) 个点，构成 \(j\) 个块（仍然是“假块”），余下可用的边数（注意这里定义反转了，不过这样好写）为 \(m\) 的方案数。有关系：

\[G(m, j) = \sum\limits_{k=m}^{c(n)} H(n, j, k) \begin{pmatrix} k \\ m\end{pmatrix}
\]

这个组合数表示在剩余的 \(k\) 条边中选出 \(m\) 条的方案数。

但我们又发现直接求 \(H\) 仍然爆炸，于是我们把 块数那一维缩掉，只保留两维。

如何加入系数 \((j-1)!(-1)^{j-1}\) 的影响？只要在转移时乘上 \(-1\) 即可。