CCPC 2020 Online

Graph Theory Class

问题重述

一个完全图，点的编号是 $1$ 到 $n$，$u$ 和 $v$ 之间的边权是 $lcm(u, v)$，求其 MST。

题解

不会啊，这题真的能做吗，为什么过了几百个队啊……

Lunch

问题重述

有若干堆石子，每次可以选一堆个数不为 $1$ 的石子，把它拆成大小相等的若干堆， 不能操作的人输。问先手必胜还是后手必胜。

题解

根据取石子游戏的一般规律，我们把各堆石子的 SG 值异或起来就行了， 所以我们只需要解决一堆石子的情况。首先，显然有

$$SG(1) = 0$$

对于 $x > 1$，如果我们将它分成偶数堆，或者分成 $x$ 个大小为 $1$ 的堆， 则分出来的这些堆的 SG 值异或起来就是 $0$；如果分成奇数个大小为 $x / d$ 的堆，则相当于只有 $1$ 堆。于是可以写出 SG 值的递推关系：

$$\DeclareMathOperator*{\mex}{MEX} SG(x) = \mex_{d \mid x, 2 \nmid d}\{0, SG(x / d)\} \quad (x > 1)$$

找规律发现，对于奇数，如果将它写成质数乘积的形式 $\prod p_k$， 则 SG 值就是这些质数的个数；对于偶数 $2^k t$，如果 $t$ 是奇数，则 $SG(2^k t) = SG(t) + 1$。

这个规律可以用数学归纳法证明，然后分解一下质因数就行了。

CCPC Training Class

问题重述

定义 $next$ 为 KMP 求出来的那个数组，$D(0) = 0$，$D(i) = D(next(i) + 1)$， 给你一堆字符，让你将它以某种顺序组成一个字符串，最大化 $D$ 的最大值。

题解

容易看出 $D(i)$ 就是在 $i$ 这个位置，使用 $i = next(i)$ 跳到串头的步数。 根据 $next$ 的性质，有 $s(next(i) + 1) = s(1)$，那么我们只要把这 $D(i)$ 步跳转的 $D(i) - 1$ 个 $s(next(i) + 1)$ 和 $s(1)$ 拿出来，放在串的开头， 就能得到一个相同大小的 $D$ 值。因此将所有相同字符连续放置一定能得到最优解， 且最优解就是最多的相同字符的个数。

Reports

签到题，略。

3x3 Convolution

问题重述

给你一个二维有限时间离散信号 $A$， 再给定一个 $3 \times 3$ 的冲激响应 $K$，用 $K$ 把 $A$ 卷积无穷次， 求结果。保证 $K$ 的 $1$-范数是 $1$，且 $K$ 的元素都非负。

题解

因为 $K$ 的 $1$-范数是 $1$，如果我们将 $A$ 看成时域无限的， 那么卷积一个 $K$ 会保持信号的 $1$-范数不变。如果 $K$ 是冲激信号， 显然怎么卷积都不改变原信号。否则，在卷积无穷次以后，原信号会被 “平摊” 到整个无限大平面上，于是信号强度会趋于 $0$。

Residual Polynomial

问题重述

已知 $f(x)$ 是多项式，求

$$(b_2 \frac{d}{dx} + c_2)(b_3 \frac{d}{dx} + c_3) \cdots (b_n \frac{d}{dx} + c_n) f(x)$$

的多项式系数。

题解

因为求导是线性运算，可以对加法进行分配，并与数乘交换次序， 因此上式中连续运用一大串算符相当于运用了这些算符的“乘积”， 结果是一个“算符的多项式”：

$$\sum_t p_t \left( \frac{d}{dx} \right)^t$$

我们可以用分治算法结合 FFT 求出 $p_t$，我们需要递归 $\mathcal{O}(\log n)$ 层，每层递归的时间复杂度都是 $\mathcal{O}(n \log n)$， 因此总的时间复杂度就是 $\mathcal{O} (n (\log n)^2)$。

然后将这个算符运用到原多项式上，我们有

$$\sum_t p_t \left( \frac{d}{dx} \right)^t \sum_k a_k x^k = \sum_t \sum_k p_t a_k k^\underline{t} x^{k-t}$$

注意到 $k^\underline{t} = \frac{k!}{(k-t)!}$， 令 $i = k - t$，可以将上面的式子变换成

$$\sum_i \frac{x^i}{i!} \sum_{k-t = i} y_t k! a_k$$

容易看出内层的和式就是两个信号的互相关函数，将其中一个进行时域反序， 就转化成了卷积，用 FFT 求一下就行了。