代码源挑战赛 Round 51 题解 - 代码源竞赛平台

T1

100%

题目要求模拟 jiangly 的 rating 变化过程。

初始 rating 为 $x$，每参加一场比赛，如果表现分为 $a_i$，则 rating 更新为 $\lfloor\frac{x + a_i}{2}\rfloor$。

由于每次更新只会依赖于前一次的 rating 和当前的表现分，我们可以直接通过一个循环，顺序遍历每场比赛的表现分 $a_i$，并不断更新 $x = (x + a_i) / 2$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$ 或 $O(n)$。

T2

100%

题目描述的操作实际上是一个“重力下落”的模拟过程：每次操作会将所有下方是空格 . 的方块 # 向下移动一格。对矩阵进行 $10^{100}$ 次操作，实际上就是让矩阵达到稳定状态，即所有的 # 都已经掉落到了不能再掉落为止。

因为方块的下落只会在同一列内发生，每一列是互相独立的。在最终的状态下，每一列所有的 # 都一定堆积在该列的最底部，而所有的 . 都浮在该列的最上方。

因此，我们可以单独处理每一列：

1. 统计第 $j$ 列中 # 的总数量，记为 $k$。
2. 将第 $j$ 列的最后 $k$ 行（即第 $n-k+1$ 到 $n$ 行）赋值为 #。
3. 将第 $j$ 列的前 $n-k$ 行（即第 $1$ 到 $n-k$ 行）赋值为 .。

时间复杂度 $O(n \times m)$。

T3

100%

利用差分数组，我们可以很方便的算出每一秒的负担值。由于要求不能有超过 $k$ 秒不蓝屏，且全程加上一个负担后每秒的相对大小不发生改变，所以我们可以将负担值从大到小排序后，（设第 $k$ 大的负担值为 $f[k]$），保证第 $k$ 秒的负担不超过 $x$ 且尽量大，也就是 $x - f[k]$ 即可。

注意如果已经满足了 $f[k] > x$，需要输出 -1。

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

T4

100%

考虑动态规划。

设 $f[i]$ 表示选出的子集的最小公倍数为 $i$ 的方案数，$n$ 的因子个数为 $d(n)$。显然答案为 $f[n]$。

首先可以确定的是，由于要让最小公倍数为 $n$，那么取的数一定是 $n$ 的因数。故取法的方案数为 $2^{d(n)} - 1$。（不考虑空集）

但是取的是 $n$ 的因数的子集的最小公倍数不一定是 $n$，但是也可能是 $n$ 的因数。所以要减掉求出来的最小公倍数小于 $n$ 的方案数。

也就是

$$f[n] = (2^{d(n) } - 1) - \sum_{(x \mid n) \cap x < n} f[x]$$

其中 $f[x]$ 的求法可以递归求解。$f$ 值存在 map 里即可。

总结一下计算的流程：

1. 先求出 $n$ 的所有因子且从小到大排序 $v_1 ,v_2,\cdots v_k$。

2. 从小到大求 $f[v_i]$：

• 先求出 $d(v_i)$ ：由于 $n$ 的因子都存在了 $v$ 数组中，所以 $v_i$ 的所有因子也在 $v$ 数组中，假设这些值分别是 $c_1 ,c_2 ,c_3 ,\cdots c_j$。（ $c$ 从小到大排序，且 $c_j = v_i$ , $d(v_i) = j$）。
• 故 $f[v_i] = (2^{j} - 1) - \sum_{k = 1}^{j - 1} f[c_k]$。

值得注意的是这个算法的复杂度。设 $D(n)$ 为 $1$ 到 $n$ 中最大的数的因子数量。那么我们会用 $O(\sqrt{n})$ 来分解因数，以及用 $O(D(n)^2)$ 来进行转移，那么这个 $D(n)$ 会是多大呢？实际上这个值并不会很多。

时间复杂度为 $O(\sqrt{n} + (\max\{{d(n)}\})^2 \log {\max\{{d(n)}\}})$。

T5

100%

本题有两个做法，$O(n)$ 以及 $O(\log n)$。

解法 1

采用正难则反（补集转化）的思想。即：求出没有任何棋子能在一步内到达 $(x,y)$ 的方案数 $W$，最终答案即为 $(4^{n \times n} - W) \pmod{666666666}$。

要使得没有任何棋子能攻击到 $(x, y)$，我们需要满足以下条件：

1. 目标格子 $(x, y)$ 必须为空。
2. 对角线上的相邻格子不能是第三种棋子。第三种棋子走斜线，与 $(x, y)$ 紧邻的至多 $4$ 个对角线格子只能是空、第一种或第二种（每个有效格子 $3$ 种选择）。
3. 所在行和列构成的 4 条射线不能有第一种、第二种棋子到达 $(x, y)$。以 $(x, y)$ 为中心，同一行和同一列被截断成了 $4$ 条射线，长度分别为 $x-1$、$n-x$、$y-1$、$n-y$。
4. 其他无关格子。其余格子无论怎么放都不会对 $(x,y)$ 产生一步威胁，各有 $4$ 种选择。

对于长度为 $L$ 的任意一条射线，能够攻击到 $(x, y)$ 有且仅有两种情况：

• 距离 $(x, y)$ 最近的第一个棋子是第一种棋子：方案数为 $\sum_{i=0}^{L-1} 4^i$。（若第一种棋子和 $(x,y)$ 中间隔了 $L - 1 - i$ 个空位，那么棋子和 $(x,y)$ 之间的格子必须是空，棋子之后的棋子可以随便取，一共有 $L - 1 - (L - 1 - i) = i$ 个位置可以随便取，故方案数为 $\sum_{i=0}^{L-1} 4^i$）。
• 距离 $(x, y)$ 最近的棋子是第二或第三种，且第二近的棋子是第二种棋子：方案数为 $\sum_{i=0}^{L-2} 2(L - 1 - i) 4^i$。（若第二种棋子和 $(x,y)$ 中间隔了 $L - 1 - i$ 个空位，第一个棋子的位置有 $L - 1 - i$ 个位置可以填，且有 $2$ 种填法，棋子之后的棋子可以随便取，故方案数为 $\sum_{i=0}^{L-2} 2(L - 1 - i) 4^i$。） 射线上不能攻击到 $(x, y)$ 的安全方案数即为 $4^L$ 减去上述两部分之和。

在代码实现中，直接使用两个常数极小的单层 $O(L)$ 循环分别计算上述两个和式。由于内部仅有简单的加减与乘法取模操作，$2 \times 10^8$ 次的规模跑的十分快。 最后，我们将对角线的方案、四条射线的安全方案、以及剩余无影响格子的方案全部相乘，即可得到没有任何棋子能够一步内到达 $(x, y)$ 的总方案数 $W$。

时间复杂度 $O(n)$。

解法 2

可以发现，上述计算的瓶颈在于计算：

$$4^L - \sum_{i=0}^{L-2} 2(L - 1 - i) 4^i - \sum_{i=0}^{L-1} 4^i$$

其中 $\sum_{i=0}^{L-2} 2(L - 1 - i) 4^i$ 是一个等差数列乘上一个等比数列求和，$\sum_{i=0}^{L-1} 4^i$ 是一个等比数列求和，我们可以利用求和公式优化这个计算式子，整理后可以得到：

$$\frac{4^{L + 1} + 6 L+ 5}{9}$$

由于模数并不是质数，所以不能直接求逆元。

一个处理方法是先计算 $(4^{L + 1} + 6 L+ 5) \bmod (9 \times P)$ 的值，然后再除 $9$。

注意运算过程可能爆 long long，需要使用 int128。

T6

100%

解法 1

考虑动态规划。

如果在构建序列的某一个时刻，我们手中拥有的青蛙数量 $\ge$ 剩余未放置的怪的数量，那么从这一刻起，无论我们怎么排列剩下的青蛙和怪，剩余的怪都一定会被我们手中的青蛙打死。也就是说，后续不可能再受到任何伤害。此时，我们可以直接停止 DP，将剩下的所有单位全排列即可。

定义 $dp[i][j][k]$ 表示已经放置了一个前缀序列，满足以下条件时的方案数：

• 还有 $i$ 只怪未放置（即已经放置了 $m-i$ 只怪）；
• 当前手中恰好有 $j$ 只青蛙；
• 已经受到了 $k$ 点伤害。

一开始所有怪都没放，手中没有青蛙，伤害为 $0$。 即 $dp[m][0][0] = 1$，其余均为 $0$。

对于当前状态 $dp[i][j][k]$，我们需要考虑下一个放置的单位是什么： 在当前状态下，我们已经消耗（打死怪）的青蛙数为 $(m-i) - k$。加上目前手中的 $j$ 只青蛙，我们总共已经放置了 $(m-i-k) + j$ 只青蛙。 因此，剩余还可以拿来放置的青蛙数量为：$have = n - (m-i-k) - j$。

1. 如果下一个放置的是青蛙： 我们有 $have$ 只不同的青蛙可以选择。放置后，手中青蛙数 $+1$。 转移：$dp[i][j+1][k] = dp[i][j+1][k] + dp[i][j][k] \times have$

2. 如果下一个放置的是怪： 我们有 $i$ 只不同的怪可以选择。

   • 如果此时手中有青蛙（$j > 0$）：青蛙会打死这只怪，手中青蛙数 $-1$。 转移：$dp[i-1][j-1][k] = dp[i-1][j-1][k] + dp[i][j][k] \times i$
   • 如果此时手中没有青蛙（$j = 0$）：我们会受到 $1$ 点伤害。 转移：$dp[i-1][0][k+1] = dp[i-1][0][k+1] + dp[i][j][k] \times i$

统计答案： 对于要求造成的伤害 $D$（$0 \le D \le m$），合法方案必然在某个时刻触发了“提前终止”条件，即达到了 $j=i$ 的状态（或者 $i=0$ 的状态，此时也满足 $j=i=0$）。 所有对应的终止状态也就是 $dp[j][j][D]$（其中 $0 \le j \le m$）。

对于特定的终止状态 $dp[j][j][D]$，我们还需要把剩下未放置的单位全排列。

• 已经放置的怪有：$m - j$ 只。
• 已经放置的青蛙有：消耗掉的青蛙 + 手中的青蛙 = $(m-j-D) + j = m - D$ 只。
• 剩余未放置的单位总数 = $(n+m) - (m-j) - (m-D) = n - m + j + D$。

因此，对答案的贡献就是 $dp[j][j][D] \times (n - m + j + D)!$。 最后将所有 $j$ 对应的贡献累加即可。

时间复杂度为 $O(m^3 + n)$。

解法 2

假设我们在一个二维坐标系中行走，从原点 $(0,0)$ 出发：

• 遇到一只青蛙（+1）：向右上走一步 $(x+1, y+1)$。
• 遇到一只怪兽（-1）：向右下走一步 $(x+1, y-1)$。

游戏总共有 $n$ 只青蛙和 $m$ 只怪兽，也就是一共要走 $n+m$ 步。 最终的终点坐标一定是 $(n+m, n-m)$。

在没有任何限制的情况下，从起点到终点的所有走法总数，就等于从 $n+m$ 步中选出 $m$ 步向下走，即总路径数为 ： $\binom{n+m}{m}$。

现在我们想求伤害恰好为 $k$ 的方案数，考虑去计算伤害 $\ge k$ 的方案，对应到二维坐标系中，也就是路径中会存在碰到 $y = -k$ 这条线的路径的方案。如何求这种方案？

假设有一条“不合法”的路径（即它触碰到了 $y = -k$），我们找到它第一次触碰到 $y = -k$ 的那个点，记为 $C$。

我们将原点 $(0,0)$ 到 $C$ 点的这一段折线，以 $y = -k$ 为对称轴，向下进行镜像翻转（反射）。

因为原点是 $(0,0)$，直线是 $y = -k$，反射后的新起点坐标就变成了 $(0, -2k)$。

任何一条从 $(0,0)$ 出发并且触碰到 $y = -k$ 到达终点 $(n+m, n-m)$ 的路径，经过上述操作后，都会变成一条从 $(0, -2k)$ 出发，到达终点 $(n+m, n-m)$ 的路径。同理， 任何一条从 $(0, -2k)$ 出发到达 $(n+m, n-m)$ 的路径，由于起点在 $y = -k$ 下方，终点在 $y = -k$ 上方（假设 $n-m \ge -k$），它必然会穿过直线 $y = -k$。我们把它第一次穿过的点前面的部分再反射回去，就一定对应了一条触碰过 $y = -k$ 的原路径。

也就是说，“触碰了 $y = -k$ 的复杂路径数” 等于 “从 $(0, -2k)$ 到终点的无限制路径数”。

无限制路径数的方案为：$\binom{n+m}{m-k}$。

现在我们想算出 $= k$ 的方案，只要将 $\ge k$ 的方案减去 $\ge k + 1$ 的方案即可。同时还要对每个不同的怪兽和青蛙进行排列，故总的方案为（$k<m-n$ 时答案为 $0$）：

$$\big( \binom{n+m}{m-k} - \binom{n+m}{m-k-1} \big) \times n! \times m!$$

由于给定的模数不一定有逆元，一种避开逆元的方案如下：

可以用下面的方法进行转换

$$\begin{aligned} \big( \binom{n+m}{m-k} - \binom{n+m}{m-k-1} \big) \times n! \times m! &= \left( \frac{(n+m)!}{(n+k)!(m-k)!} - \frac{(n+m)!}{(n+k+1)!(m-k-1)!} \right) \times n! \times m! \\ &= \frac{(n+m)!}{(n+k+1)!(m-k)!} \big[ (n+k+1) - (m-k) \big] \times n! \times m! \\ &= \left( \frac{(n+m)!}{(n+k+1)!} \right) \times \left( \frac{m!}{(m-k)!} \right) \times n! \times (n - m + 2k + 1) \end{aligned}$$

这样就只需要计算 $\frac{(n+m)!}{(n+k+1)!}$ 和 $\frac{m!}{(m-k)!}$ 即可，这两个部分可以直接通过乘法得到。

时间复杂度为$O(m^2 + n)$。

T7

100%

题目要求计算的表达式为：

$$\sum_{i=1}^n \sum_{j=1}^i \operatorname{lcm}(i,j) \binom{i}{j}$$

根据最小公倍数和最大公约数的性质，有 $\operatorname{lcm}(i,j) = \frac{i \times j}{\gcd(i,j)}$。代入原式得：

$$\sum_{i=1}^n \sum_{j=1}^i \frac{i \times j}{\gcd(i,j)} \binom{i}{j}$$

我们可以改变枚举顺序，改为枚举 $d = \gcd(i,j)$：

$$\sum_{d=1}^n \frac{1}{d} \sum_{i=1}^n \sum_{j=1}^i [\gcd(i,j)=d] \cdot i \cdot j \cdot \binom{i}{j}$$

定义 $g(d) = \sum_{i=1}^n \sum_{j=1}^i [\gcd(i,j)=d] \cdot i \cdot j \cdot \binom{i}{j}$。那么最终的答案即为 $\sum_{d=1}^n g(d) \cdot d^{-1}$。

为了求出 $g(d)$，我们可以先放宽条件，定义 $f(d)$ 表示仅仅满足 $i, j$ 是 $d$ 的倍数时的求和（不要求 $\gcd$ 恰好等于 $d$）：

$$f(d) = \sum_{u=1}^{\lfloor n/d \rfloor} \sum_{v=1}^u (ud)(vd) \binom{ud}{vd}$$

当我们求出了所有的 $f(d)$ 后，就可以利用容斥原理（或者莫比乌斯反演/倒推），从后往前减去多算的严格倍数的部分，从而得到真实的 $g(d)$：

$$g(d) = f(d) - \sum_{k=2}^{\lfloor n/d \rfloor} g(k \cdot d)$$

接下来核心的问题是如何快速计算 $f(d)$。我们将组合数展开：

$$f(d) = \sum_{u=1}^{\lfloor n/d \rfloor} \sum_{v=1}^u (ud)(vd) \frac{(ud)!}{(vd)!((u-v)d)!}$$

令 $k = u$，$i = u - v$（即 $v = k - i$），式子可以改写为：

$$f(d) = \sum_{k=1}^{\lfloor n/d \rfloor} (kd)(kd)! \sum_{i=0}^{k-1} \frac{(k-i)d}{((k-i)d)!} \cdot \frac{1}{(id)!}$$

这可以通过调换求和顺序，转为：

$$f(d) = \sum_{i=0}^{\lfloor n/d \rfloor} \frac{1}{(id)!} \sum_{k=i+1}^{\lfloor n/d \rfloor} \Big( (kd)(kd)! \Big) \cdot \Big( \frac{(k-i)d}{((k-i)d)!} \Big)$$

令数组 $a[k] = (kd)(kd)!$，数组 $b[v] = \frac{vd}{(vd)!}$。那么内层求和实际上是 $\sum_k a[k] b[k-i]$。

注意到其差值是一个定值，故考虑用 NTT 来求值。

令 $m = \lfloor n/d \rfloor$。我们将数组 $b$ 进行翻转，得到新数组 $b_{rev}[x] = b[m - x]$。 那么原式中的 $b[k-i]$ 就可以写成 $b_{rev}[m - k + i]$。 此时 $k + (m - k + i) = m + i$ 是一个定值。直接做多项式乘法即可。

对于给定的 $d$，多项式的长度为 $m = \lfloor n/d \rfloor$，进行 NTT 的时间复杂度为 $O(\frac{n}{d} \log \frac{n}{d})$。 我们对所有的 $d \in[1, n]$ 都要做一次 NTT，总的时间复杂度为：

$$\sum_{d=1}^n O\Big(\frac{n}{d} \log \frac{n}{d}\Big) \approx O(n \log^2 n)$$