2018 Multi-University, HDU Day 4

Problem A

Upsolved by ultmaster.

题意：一个数是好数当且仅当比它小的且因数个数比它多的数不超过 $K$ 个。求第 $n$ 个不好的数。

题解：此题是一个之前没补的题：2015-2016 Makoto rng_58 Soejima Сontest 4 的 A 的加强版。一石二鸟把两个题都补了。

首先这个好数是不多的，大概在导致即使询问在 $10^{18}$，答案也就在 $10^{18}+10^5$ 的规模。所以考虑用一种快速的暴力求出所有的好数。

其次考虑一个数一旦不是好数，这个数所有的倍数也不是好数（因为所有比它小的，害它不是好数的数，同样也会加倍）。基于这点考虑，增加很多质因子是没有好处的，我们可以维护一个已经找到的好数的集合，然后从小到大枚举质因子，不断扩充这个集合。当然这个扩充完的集合肯定不是每个数都合法的，我们每次扩充完毕之后，还要从这个集合里面筛掉一点。

那么怎么筛掉呢？如果用原有的性质，即逐一检查比它小的所有数的因子个数，在这个数据规模下肯定是来不及的。其实有下面的结论：$x$ 有不超过 $K$ 个比它小的数因子数比它多，那么这些比它小的数肯定每个都在候选列表里。我们可以使用反证法证明这个结论：如果不在列表里，有一个不在列表里的数 $y<x$ 满足因子比 $x$ 多，又因为不在列表里，它有超过 $K$ 个比它小的数因子数比 $y$ 多，那么至少有 $K+1$ 个数小于 $x$ 且因子比 $x$ 多，矛盾。所以我们进行筛选的时候，就只依赖于这个列表中的数了。从小到大枚举这个列表中的数，然后维护因子数前 $K+1$ 大的，如果 $x$ 的因子数比第 $K+1$ 大的因子数都小，那么就跳过，否则把 $x$ 加入下一轮的答案，并将 $x$ 的因子数加入集合。

几个细节：质因子大概加到 350 左右就不再有用了，可以直接退出；乘的时候要注意经典的防爆 LL；实现还是比较紧的，全部用 set 实现的话可能会超时，建议能开数组的地方全部开数组，由于质因子是从小到大枚举的，所以不会有去重的问题，新加进来的数直接存在后面，然后 sort 就好了；刚开始直接算 233 的答案，最后存答案的时候，从大到小枚举 $K$，逐步筛选，用 234 个 vector 记录所有答案，由于 $K$ 的时候的答案集合一定是 $K+1$ 的时候的答案集合的子集，所以这样做是正确的。同时注意到 $K$ 越小的时候答案越少，所以总个数并不多。

另外回答询问的时候，std 采用了某种技巧，往答案里填数的时候减去了一个下标，可以一个 log。但是直接二分套二分两个 log 也能过（这不是瓶颈）。

Problem B

Solved by zerol. 03:24 (+2)

题意：求 $f(n,m)=\sum_{i=0}^m \binom{n}{i}$ 范围和询问都是 1e5。

题解：$f(n,m)$ 可以 $O(1)$ 转移到 $f(n\pm 1,m)$ 和 $f(n,m\pm 1)$，然后莫队。

zerol：为了防止零贡献，抢了这题来写，然后犯了愚蠢至极的错误，模意义下我竟然写了 /2，（手动自裁）。

Problem C

Upsolved by ultmaster.

题意：给一棵树，边上有权值 1,2,3。在树上走路必须遵循 (1*3)?[12]* 的模式。每次操作先令 $w(a,b) = \max(1, w(a,b)-1)$，然后求 $s$ 到 $t$ 有没有路，$s$ 到多少点有路。

题解：初一看并查集似乎很显然，维护 1 的块，维护 1 和 2 的块，维护 1 的块相邻的 2 的块的大小总和。但是很显然不会维护。。。看了 dls 的讲解（内容就是反复强调这个题真的简单）之后发现没有利用到树的性质。其实对于每个节点只需要维护孩子的信息即可。父亲的信息在询问的时候另外算（这和一般图是不一样的）。树上并查集也是多校中第二次碰到了。保持并查集的结构和树的结构的一致性，并查集合并的时候要有向合并，使得合并之后节点的父亲仍然可查（没有注意方向 WA1）。

ultmaster: WA 了好久，又犯了修 bug 修一半的错误，并查集的信息永远维护在根节点上，查询的时候一定要传根。后来写了个函数如果发现不是根就再调用一次 find。用到两个有一点点不一样的并查集（写了个继承）。有数据也因为规模太大，完全没有帮助调试，最后还是对了拍（捂脸）。注意查父亲的时候一定要检查跟父亲连的那条边是不是 3（有一发 WA 在这里）。

Problem D

Solved by ultmaster. 01:02 (+2)

题意：有 $n$ 道题目，每道题目有 $a_i$ 个正确答案和 $b_i$ 个错误答案。现在有 $n$ 个人，设计合理策略使得最高分最大。

题解：简单地认为策略是笛卡尔乘积。出了个假算法过了。

zerol: 必须要喷，___出题人，出假题导致 WA 到怀疑人生（虽然也不一定是正解），发现不对 std 假了就魔改题面，然后还是假的就加样例解释。好在队友 ultmaster 与出题人心有灵犀，一下子就 A 了。

ultmaster: 和 ___出题人 心有灵犀，我也是 ___？

Problem E

Solved by kblack. 02:32 (+)

题意：按斜角在一个无限矩阵中放置一个数列，求子矩阵的和。

题解：循环节为 $2L$，求前缀和以后分区域求和即可。

Problem F

Upsolved by zerol.

题意：支持把格子 x 涂黑，黑色往左右蔓延 x 个距离，把 l~r 翻转，回溯到某个操作，询问某个位置有没有涂黑。

题解：持久化数据结构。用左右括号覆盖所有黑色区域（不考虑覆盖的次数）。问题转化成支持插入一对括号，所有括号左右移动，插入若干个括号后中间一段翻转后（左->右，右->左），查询某个位置前括号总数量。实现难点：区间的闭开（尤其是翻转的时候），带 pushdown 的持久化不好写（要修改，先复制）。翻转看做沿 y 轴对称，这样可以少维护一个量（不然有 a-x,a+x）。

Problem G

Solved by zerol. 04:53 (+5)

题意：问一棵树的所有可能的 dfs 序中有多少比给定序列小。

题解：类似于数位 dp 的想法，每次固定给定序列的一位，然后下一位比给定序列小，计数后累加入答案。一棵树 dfs 序总数是 $\prod_u son[u]!$（$son[u]$ 表示 u 的儿子个数），如果 dfs 序的前若干个已经确定了（也就是一些点已经访问了），那么在这个状态下的 dfs 序总数就是————访问过的点不计入父亲的儿子总数中，然后带入公式。维护一个全局变量 S，表示当前的 dfs 序总数，然后按照给定序列进行访问，每次访问都会使 S 除以访问的点的父亲当前儿子数，然后需要计算有几个儿子比给定序列中下一个位置的元素小，这一部分用个数据结构就好了（推荐 pb_ds)。如果有已访问结点的儿子没访问完，那么剩下的给定序列已经无法构成合法 dfs 序了，那么退出。由于根是任意的，所以那一部分要分开算，然后以给定序列的第一项为根进行 dfs 计数。

zerol：比官方题解简单的体现就是不用从父亲计算贡献。也就是不用维护每棵子树的 dfs 序数量，而是维护一个全局的当前 dfs 序数量，因为这个计数是可减而且和顺序无关的。

Problem H

Upsolved by kblack.

题意：一个排列围成一个圈，一个人绕圈按概率拿起数字，组成一个新排列，求新排列的大小（按字典序排序的序数）的期望值。

题解：不如直接看官方题解，官方题解好评，除了一个地方稍微脑补一下以外，其他地方都十分详尽。主要思路是，把完整的式子写出来，然后强力化简，措施包括但不限于暴力展开二项式和提取辅助函数，式子长得一批，还要注意各个函数定义域别漏求了。

Problem I

Upsolved by ultmaster.

题意：$ans = \sum_{i = 1} ^ {N} {[\gcd(i, N) = 1] \sum_{j = 1} ^ {i} {j ^ K}}$

题解：官方的题解已经说得非常清楚了。这里再补充几点。

1. $G_i$ 化到最后出来应该是 $\sum_{j=1}^{K+1} \sum_{k=1}^{K+1} [j-k=i] \frac{B_{i+1}^+}{(i+1)!} K! \frac{B_{K+1-j}^+}{(K+1-j)!} \frac{N^k}{k!}$。题解里最不好的地方就是用了小 $k$ 和大 $K$，写在纸上根本搞不清楚。里面的 $K!$ 之类的项可以直接待在里面算，时限好像不是很紧。

2. 最后预处理伯努利数需要用到「集训队论文」中的科技，使用 NTT 进行优化，具体原理我也没细看（意识模糊了）。特别注意 $B^-$ 和 $B^+$ 在第一项上的区别。（两个板子在这个事情上都是有问题的，以为拍过了，然后对着空气调试。）

3. $i=-1$ 以及式子形式的特殊性有可能在转化卷积上带来一点困难。还是要采用「纸带法」，仔细检查每一个数应该放在哪儿，卷完以后会落到哪儿，千万不要凭运气去试。

4. 当然这道题最难的地方应该还是在前面的数学上。大概没有题解就不会做题了吧。

UPD: 官方题解搬运。

莫比乌斯反演：

[math]\displaystyle{ \begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {N} {[d \mid i] \sum_{j = 1} ^ {i} {j ^ K}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} {d}} \sum_{j = 1} ^ {id} {j ^ K}} \end{aligned} }[/math]

ultmaster's comment: 直接容斥就好了，用不到反演公式（当然强行用大概也行）。

定义 $F$：$F_p(N) = \sum_{i = 1} ^ {N} {i ^ p}$，显然 $F_p$ 是 $p + 1$ 阶多项式：$F_p(N) = \sum_{i = 0} ^ {p + 1} {a_{p, i} N ^ i}$。

ultmaster's comment: 其实这个多项式的零次系数恒为 0。

利用 $F$ 化简原式：

[math]\displaystyle{ \begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} {d}} {F_K(id)}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} {d}} \sum_{j = 0} ^ {K + 1} {a_{K, j} (id) ^ j}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j \sum_{i = 1} ^ {\frac{N} {d}} {i ^ j}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j F_j(\frac{N}{d})}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j \sum_{k = 0} ^ {j + 1} {a_{j, k} (\frac{N} {d}) ^ k}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = -1} ^ {K + 1} {d ^ i \sum_{j = 0} ^ {K + 1} \sum_{k = 0} ^ {j + 1} {[j - k = i] a_{K, j} a_{j, k} N ^ k}}} \end{aligned} }[/math]

定义 $G$：$G_i = \sum_{j = 0} ^ {K + 1} \sum_{k = 0} ^ {j + 1} {[j - k = i] a_{K, j} a_{j, k} N ^ k}$

利用 $G$ 化简原式：

[math]\displaystyle{ \begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = -1} ^ {K + 1} {d ^ i G_i}} \\ & = \sum_{i = -1} ^ {K + 1} {G_i \sum_{d \mid N} {\mu(d) d ^ i}} \\ & = \sum_{i = -1} ^ {K + 1} {G_i \prod_{p \mid N} {(1 - p ^ i)}} \end{aligned} }[/math]

ultmaster's comment: 第二次容斥（大概还是不用反演）。

如果我们能快速计算出 $G$，就可以在 $O(MK)$ 的时间计算答案，其中 $M$ 为质因子个数。

将 $G$ 用伯努利数展开，可以发现是卷积的形式，直接 NTT，时间复杂度 $O(K \log K)$。

Problem J

Solved by ultmaster. 02:13 (+)

题意：给一个每一块都有可能转坏了的 16 进制数独，让你把它转回来。

题解：送温暖的简单模拟题。由于题目没读清楚（只看了图）顺时针和逆时针搞反了调了半天，浪费半小时。

Problem K

Solved by ultmaster. 00:48 (+1)

题意：填 ? 使得表达式合法。

题解：把符号归成三类：1-9，0，+*。大概有三条规则：1. 刚开始和最后不能是 0；2. 0 后面必须是 +*；3. +0/*0/刚开始的 0 后面必须是 +*。使用这三条规则可以计算出每一位上可能的符号。然后一位一位填即可。注意好像不会发生冲突所以不用迭代到收敛；另外填的时候要注意不能篡改原式（没考虑到 WA1）。

Problem L

Solved by ultmaster. 00:07 (+)

温暖的签到题。（今天签的这么多一定是因为 kblack 迟到了。）