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

# [CCPC 2020 Online](http://acm.hdu.edu.cn/search.php?field=problem&key=2020%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC%A3%A8CCPC%A3%A9+-+%CD%F8%C2%E7%D1%A1%B0%CE%C8%FC&source=1&searchmode=source)

## [Graph Theory Class](http://acm.hdu.edu.cn/showproblem.php?pid=6889)

### 问题重述

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

### 题解

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

## [Lunch](http://acm.hdu.edu.cn/showproblem.php?pid=6892)

### 问题重述

有若干堆石子，每次可以选一堆个数不为 $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](http://acm.hdu.edu.cn/showproblem.php?pid=6894)

### 问题重述

定义 $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](http://acm.hdu.edu.cn/showproblem.php?pid=6897)

签到题，略。

## [3x3 Convolution](http://acm.hdu.edu.cn/showproblem.php?pid=6898)

### 问题重述

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

### 题解

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

## [Residual Polynomial](http://acm.hdu.edu.cn/showproblem.php?pid=6900)

### 问题重述

已知 $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 求一下就行了。
