2018 Multi-University Training Contest 10

Problem A

Upsolved by ultmaster.

题意：求烷烃、烷基的同分异构体数量。

题解：仔细论证 / OEIS 可以得到烷基个数有生成函数 $A(x) = 1 + \frac{1}{6}x (A(x)^3 + 3A(x)A(x^2) + 2A(x^3)$。用分治 FFT 可以解 $A(x)$（怎么解？）。烷基个数可以由： $P(x) = \frac{1}{24} x (A(x)^4 + 3A(x^2)^2 + 6A(x)^2 A(x^2) + 8A(x) A(x^3) + 6A(x^4))$, $Q(x) = \frac{1}{2} ((A(x) − 1)^2 + A(x^2) − 1)$, $B(x)=P(x)-Q(x)+A(x^2)$ 给出。（题解中有个错误，应该是 $A(x)^4$ 而不是 $A(x^4)$。）

跟标程反复对照，反复（尝试）理解之后 AC 了。不少细节还是没有搞清楚。难点在于这个分治：CDQ 分治时，利用已经算好的 $[l,mid]$ 计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。一般来说，对于 $mid + 1 \le i \le r$ 来说 $f(i) = \sum_{j=l}^{mid} f(j) a_{t-j}$，此处 $t$ 是一个定值，$a$ 数组也应该是已经算好的东西。但此题的麻烦之处在于 $a$ 数组是一个跟 $f$ 有关的东西，而且并不总是算好了的。举例来说，对于 $A(x) A(x^2)$ 来说，$A(x^2)$ 依赖的数值比较靠前一定计算完成了。但对于 $A(x)^3$，我们写成 $A(x) \cdot A^2(x)$ 的形式，需要的是 $[mid+1,r]$，$A(x)$ 在 $[l,mid]$ 之间，此时 $A^2(x)$ 在 $l=0$ 的时候还没算完，而且差的是靠后面的项。但是由于是 $A^3(x)$，我们可以在后面（$l$ 不为 0 的时候）算贡献的时候补回来，具体是乘一个系数 3（为什么是 3？）。

算完 $A(x)$ 以后，$B(x)$ 应该不难算出。细心一点不要抄错。

Problem C

Upsolved by ultmaster. (-32)

做自闭了。

题意：求 $\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \text{gcd}(i,j^2,k^3)$。

题解：枚举 gcd，然后类比 $(i,j,k)$ 的做法，考虑求出每个数的 g2, g3，分别定义为对于每个数的质因数上的指数除以 2 和除以 3 取上整得到的数。朴素的做法是 $\sum_{i=1}^n \phi ( g ) \sum_{k=1}^{n/i} \mu(k) \lfloor A / (ig) \rfloor \lfloor B / g_2(ig) \rfloor \lfloor C / g_3(ig) \rfloor$。可以交换求和符号优化这个过程（预处理一些东西然后每个 case 是线性的），得到 $\sum_{i=1}^n f(i) \lfloor A / i \rfloor \lfloor B / g_2(i) \rfloor \lfloor C / g_3(i) \rfloor$，其中 $f(i) = \sum_{d|i} \mu(d) \phi(i/d)$。考虑优化这个 $f(i)$ 的计算过程（去掉 log），由于是积性函数的狄利克雷卷积，所以该函数也是积性的。所以可以使用线性筛。筛的时候在加入相同的因子的时候，如果是质数的幂 $p^x$，则 $f(k = p^{x+1})= \phi(p^{x-1}) + \phi(p^x) - f(p^x)$；否则直接相乘。

线性的牛逼啊，但这个超小的 log 在本地两秒就能跑出来的，在 HDU 上就是怎么也过不了。优化来优化去甚至加入了 cache 优化还是 TLE。时限这么紧导致线性复杂度也会 TLE。赛后对着这个线性的又是一通优化才过。过的提交就没有一份在 1/2 时限内跑出来的。卡常卡得让人怀疑我是谁我在哪儿我为什么会在这儿。

Problem E

Solved by zerol. 01:18 (+2)

题意：对于树上的每个点，求 lca 恰好是这个点的点对中点权 gcd 的最大值。

题解：对于树上每个点，求出一个 bitset 记录了子树中所有数的因数并，然后依次合并儿子以及自己本身，合并前取位与检查最高位的 1。（bitset._Find_first() 可以求出第一个 1 的位置。）

另解：线段树合并 / set 启发式合并。枚举 gcd 在更新在虚树上结点的答案（相邻两项 LCA）（由 CSL 友情提供）。

Problem G

Solved by OEIS. 00:42 (+)

Problem H

Solved by ultmaster. 00:08 (+)

题意：求 $2^n$。

题解：高精度。或

printf("%.0f\n", pow(2, n));

Problem I

Solved by kblack. 00:51 (+)

题意：$\sum_{i=1}^{n}{\sum_{j=1}{i-1}{[gcd(i+j, i-j) = 1]}}$。

题解：若 $i$ 与 $j$ 奇偶性相同，肯定凉了，否则 $gcd(i+j, i-j) = gcd(i+j, 2j) = gcd(i+j, j) = gcd(i, j)$，即 $i$, $j$ 互质即可。若 $i$ 是偶数 $phi(i)$ 即可，若 $i$ 是奇数，那么 $\frac{phi(i)}{2}$ 就可以了，线性筛一下求个前缀和就好。

Problem J

Solved by zerol. 02:19 (+4)

题意：对于两个点集 S_1, S_2，求 $\max\{dist(x,y)+w_x+w_y | x\in S_1,y\in S_2\}$，距离为曼哈顿距离，最多五维。

题解：K-D Tree 暴力，要多加一些剪枝才能过。

正解：枚举每一维绝对值的正负，记录 $2^5$ 种可能的最大值，将另一个点集带入，取最大值即可。

Problem L

Solved by kblack. 01:21 (+)

题意：最多 $K$ 个人看电影，每个电影能拿钱，连续看相同类型的电影要罚钱，求最大获益。

题解：两排点表示在看那种电影，对于每个电影在两边对应时间连边，再连上发钱切换的边，费用流一下就好了。