本系列不定期更新，每个 Part 约有 $6 \sim 8$ 题，一般一个专题一个 Part，具体题目数量视标签个数而定。
8/5 T1 絶対、大丈夫！
设原数为 $\overline{a_1a_2a_3 \cdots a_n}$，明显，$P = \sum_{i=1}^{n} a_i \times (10^i-10^{p_i})$，其中 ${p_1, p_2, \cdots, p_n}$ 是 $1 \sim n$ 的一个排列。
经过简单推导易证对于任意 $x, y \in \mathbb{N}$，$(10^x-10^y) \bmod 9 = 0$，故 $P \bmod 9 = 0$。
能被 $9$ 整除的数各位数加起来一定为 $9$ 的倍数。又因为删去的一位数不为 $0$，所以删去的那一位数是唯一的。答案即为 $9 - P \text{的数位和} \bmod 9$。
再考虑构造解。由于 $P \bmod 9 = 0$，于是设 $T = \frac{P}{9}$（带前导零），$S=10T$，容易证明 $S-T=P$ 且组成 $S$，$T$ 的数字相同。由于允许前导零，直接输出 $S$，$T$ 即可。
1 |
|
8/6 T2 まるゆ，潜航 ！
设 $1 \sim n-1$ 号まるゆ运输的货物的类型的并集 $U$ 大小为 $u$，交集 $V$ 大小为 $v$，明显有 $0 \leq v \leq u \leq k-1$。
答案即为：
$$
\sum_{u=0}^{k-1} \sum_{v=0}^{u} \binom{k}{u} \binom{u}{v} \left( 2^{n-1}-2 \right)^{u-v} 2^{k-v} (2^k-2^u)
$$
对每个部分单独解释：
- $\binom{k}{u}$、$\binom{u}{v}$：从 $k$ 个货物里选 $u$ 个作为并集，从 $u$ 个货物里选 $v$ 个作为交集。
- $(2^{n-1}-2)^{u-v}$：分成三种情况考虑。
- 1、对于交集内的物品：$1 \sim n-1$ 号まるゆ必须全部选这个物品。
- 2、对于不在并集内的物品：$1 \sim n-1$ 号まるゆ必须都不选这个物品。
- 3、对于在并集，不在交集内的物品：$1 \sim n-1$ 号まるゆ不能都选或都不选这个货物，剩下方案随意，故此部分贡献为 $(2^{n-1}-2)^{u-v}$。
- $2^{k-v}$：对于 $0$ 号まるゆ，他不能选 $V$ 内的物品，否则就不满足限制 1。剩余货物随意，故此部分贡献为 $2^{k-v}$。
- $2^k-2^u$：对于 $n$ 号まるゆ，他不能同时选择不在 $U$ 内的物品，否则就不满足限制 2。剩下货物随意，故此部分贡献为 $(2^{k-u}-1) \times 2^u = 2^k - 2^u$。
接下来就是化简，疯狂二项式定理，一顿操作猛如虎：
$$
\begin{align}
Ans = & \sum_{u=0}^{k-1} \sum_{v=0}^{u} \binom{k}{u} \binom{u}{v} (2^{n-1}-2)^{u-v} 2^{k-v}(2^k-2^u)\\
= & \sum_{u=0}^{k-1} \binom{k}{u}(2^k-2^u)2^k \sum_{v=0}^{u} \binom{u}{v} (2^{n-1}-2)^{u-v} \left(2^{-1}\right)^v\\
= & \sum_{u=0}^{k-1} \binom{k}{u}(2^k-2^u)2^k(2^{n-1}-2+2^{-1})^u\\
= & 4^k \times \sum_{u=0}^{k-1} \binom{k}{u} (2^{n-1}-2+2^{-1})^u 1^{k-u}-2^k \times \sum_{u=0}^{k-1} \binom{k}{u} (2^n-3)^u 1^{k-u}\\
= & 4^k \times [(2^{n-1}-1+2^{-1})^k-(2^{n-1}-2+2^{-1})^k] - 2^k [(2^{n}-2)^k-(2^{n}-3)^k]\\
= & (2^{n+1}-2)^k-(2^{n+1}-6)^k-(2^{n+1}-4)^k+(2^{n+1}-6)^k\\
= & (2^{n+1}-2)^k-(2^{n+1}-4)^k\\
\end{align}
$$
快速幂计算即可。
时间复杂度：$\mathcal{O}(T \log^2 k)$。
代码：
1 |
|
9/14 T2 大凤号装甲空母
先给出一种比较友好的思考方法。
设 $x = \frac{\sqrt{5}+1}{2}$，使用计算器计算 $x^n$，可以发现几个性质：
- $x^n + x^{n+1} = x^{n+2}$
- $|x^n - \operatorname{round}(x^n)|$ 逐渐变小，其中 $\operatorname{round}(a)$ 表示四舍五入。
设 $f(x) = \lfloor x^n \rfloor$，$\epsilon(x) = [x \bmod 2 = 1]$，再经过仔细观察后不难得到：$f(x) = f(x - 1) + f(x - 2) + \epsilon(x)$。
如果舍去 $\epsilon(x)$ 一项，则该式是经典的 Fibonacci 数列，可以用矩阵乘法求出。但其实 $\epsilon(x)$ 函数有性质 $\epsilon(x) = \epsilon(x - 2)$，于是乎：
$$
\begin{bmatrix}
f(n-1) & f(n) & \epsilon(x-1) & \epsilon(x)
\end{bmatrix}
=
\begin{bmatrix}
f(n-2) & f(n-1) & \epsilon(x-2) & \epsilon(x-1)
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}
$$
矩阵快速幂即可，时间复杂度 $\mathcal{O}(4^3 \times \log n)$。
代码：
1 |
|
std 的特征根法得咕一会…
8/7 T3 最大割
Hexo nmd 竟然不支持 \bold{}…
首先，期望就等于边权 $\times$ 两个点不在同一集合的概率。
列出式子可得：
$$
\begin{align}
E(maxcut) = & \sum_{(i,j) \in E} a_{i,j} \times \left[\left(\frac{1}{2} \times (1 + \varphi_s(\langle \mathbf{u_j, Z} \rangle))\right) \times \left(\frac{1}{2} \times (1 - \varphi_s(\langle \mathbf{u_i, Z} \rangle))\right) + \left(\frac{1}{2} \times (1 + \varphi_s(\langle \mathbf{u_i, Z} \rangle))\right) \times \left(\frac{1}{2} \times (1 - \varphi_s(\langle \mathbf{u_j, Z} \rangle))\right)\right] \\
= & \sum_{(i,j) \in E} a_{i,j} \times \left[\frac{1}{2} \times (1-\varphi_s(\langle \mathbf{u_i, Z} \rangle)\varphi_s(\langle \mathbf{u_j, Z} \rangle)) \right]
\end{align}
$$
设 $r_i = \langle \mathbf{u_i, Z} \rangle$，将 $r_i$ 按绝对值升序排序。
注意到 $E(maxcut)$ 是一个关于 $\frac{1}{s}$ 的二次函数，且在 $[r_i, r_{i+1}]$ 中连续均匀。考虑暴力计算系数，分段求最值，单次时间复杂度 $\mathcal{O}(n^3)$，不够优秀。
再注意到在 $[r_i, r_{i+1}]$ 转移至 $[r_{i+1}, r_{i+2}]$ 时，只会有一个点的 $\varphi_s$ 值发生变化，于是只计算这一个点的影响，就能将单次时间复杂度降为 $\mathcal{O}(n^2)$。
代码：
1 |
|
8/12 T3 Math
提高组出 Miller-Rabin，出题人真厉害
考虑 Miller-Rabin + Pollard-rho，但是如果出题人恶意构造数据的话 Pollard-rho 会退化为 $\mathcal{O}(\sqrt{n})$。
所以考虑以下思路：先将 $a_i$ 所有 $10^6$ 以内的因子筛除，那么筛除过后，$a_i$ 的值就只会有三种情况：（1）质数，（2）质数的完全平方，（3）两个不同质数的积
但是直接计数的话会重复计算在所有 $a_i$ 中出现多次的质数，所以我们还需要先筛除所有出现多次的质数。具体实现很简单，因为现在 $a_i$ 最多由两个质数相乘而得，所以两两之间求 $\gcd$ 就相当于计算哪些质数出现了多次。
再筛去这些质数后，就可以直接计数求贡献了。
时间复杂度 $\mathcal{O}(10^6 + cn \log^3 SIZ + n^2 \log SIZ)$，其中 $c$ 为 Miller-Rabin 的测试次数，$SIZ$ 为值域 $10^{18}$。
注意：两两求 $\gcd$ 时求出的 $\gcd$ 可能不是质数，一定要注意这一情况！
代码：
1 |
|