ccpc-2020-online.md 4.3 KB

+++ date = "2020-09-24T20:05:00+08:00" draft = false tags = [] title = "CCPC 2020 Online" authors = ["xry111"] +++

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$,可以将上面的式子变换成

$$\sumi \frac{x^i}{i!} \sum{k-t = i} y_t k! a_k$$

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