2018 Multi-University, Nowcoder Day 7

Problem A

Solved by zerol. 00:22 (+)

题意：求一个 1~n 到 1~n 的匹配，使得位与的和最小。

题解：首先猜想答案一定是 0（考虑每一位，0 的个数都不小于 1 的个数，所以不排除答案是 0 的可能性）。然后开始构造，发现 $2^k+i$ 和 $2^k-i-1$ 匹配是极好的，然后就找到当前不超过 n 的最大的 k，这样大于等于 $(2^k - 1)-(n-2^k)$ 的就搞定了，然后接着处理变小了的 n 就好了。

Problem C

Solved by ultmaster. 02:14 (+3)

题意：给一个长度为 $2^n$ 的字符串，每次用 AND, OR, XOR 中的一种操作把相邻的两个合并。求最后合并结果是 1 的操作方案数。

题解：暴力就好了，维护一个可选的集合，和集合中每个产生的方案数。复杂度是 $\sum_{x=0}^{18} 2^{18 - x} \cdot \min(3^x, 2^{18-x}) \approx 1.4 \times 10^7$。由于还要带上数据结构的常数 / log，可能时限很紧。需要常数优化，能少开的地方尽量少开，unordered_map 可以卡过。

Problem D

Upsolved by ultmaster. (-1)

题意：有关于 $b$ 的方程 $t = a^n x + b (\sum_{i=0}^{n-1} a^i) \bmod p$。请构造一组 $(x,n,t,p)$ 使得：$p \le M$ 且使 $b$ 有解的 $a$ 尽可能大（即存在 $a$ 满足代入之后 $b$ 有解，且满足所有 $a' < a$ 代入之后都无解）。

题解：这种题就是属于做不出来的。比赛的时候甚至连上面的题意都没分析出来。切入点是从小到大枚举 $a$ 的情况分析 $b$ 的有解条件（就是枚举着枚举着突然有一天 $b$ 就有解了，我们要让这一天尽可能来得晚）。注意到只有 $p$ 是有限制的，所以这个方程里的 $x,n,t$ 都是想选什么就选什么。

• 首先最惨的情况是 $a=1$ 就有解了。那么有 $(x + nb) \bmod p = t$，由于 $n$ 是想选什么就选什么，所以要么 $x=t$，要么 $\text{gcd}(n,p)=1$ 即 $n \bmod p \ne 0$。所以无解的条件是 $x \ne t$ AND $p | n$（条件 0）。
• 其次 $a>1$。那么有 $(a^n x + \frac{a^n-1}{a-1} b) \bmod p = t$。那么有解条件就是：$a^n x \equiv t \pmod p$ OR $\frac{a^n-1}{a-1} \bmod p \ne 0$，即 $a^n \ne 1 \pmod p$。所以 $b$ 无解的情况是 $a^n x \ne t \pmod p$ AND $a^n \equiv 1 \pmod p$，注意到如果 $n = p - 1$ 的话，那就什么都有解了，为了让 $a$ 小的时候无解，$n$ 坚决不能等于 $p-1$（条件 1），其次可以令 $x=p, t=1$，这样的话无解的第一个式子就满足，这时候只需要考虑第二个式子。就是（条件 2）要求一个不是 $p-1$ 的倍数的数 $n$，使得 $a'^n \equiv 1 \pmod p$（对于 $a' < a$）。然后最后这个 $n$ 求出来了以后我们只要验证一下有解条件成立就好了（条件 3）。至于这个 $a$ 的话，根据原根的定义可以知道，肯定不会比原根大的。

然后我们就是要找一个符合 0,1,2,3 这四个条件的 $n$，要把比 $a$ 小的所有的 $a'$ 在模 $p$ 意义下的阶，以及 $p$ 本身做一次 lcm，边做便要验证条件 1，做完了以后再验证下条件 3 就好了。实现起来其实挺容易的，但是如果暴力的话时限其实有点紧。（不过反正可以交表嘛。。。）

ultmaster: 一早就过了这个题拿了一血的 oxx 说其实就是原根，乱搞一下就好了。并且对题解没有采用他的代码表示很不满。然后我直接当原根乱搞一下 WA 了。求到原根以后又枚举了一下（其实是两下）才过。可能就是太菜了吧。事实上如果题解采用了 oxx 的代码我可能连怎么死的都不知道（少枚举了一次只炸了一个但死活看不出来）。

Problem E

Solved by ultmaster. 03:07 (+1)

题意：构造一个不超过 75 个点的图，使得刚好有 $n$ 个 $K_4$ 子图。

题解：不失一般性，我们只讨论最大的情况。分成 70 个点，和 5 个点。70 个点构成完全图有 $\binom{70}{4}$，然后五个点分别射进去 $x_1,x_2,\ldots,x_5$ 个，就可以多得到 $\binom{x_1}{3}, \ldots, \binom{x_5}{3}$ 个 $K_4$。故 $\binom{70}{4} + \binom{x_1}{3} + \cdots + \binom{x_5}{3} = n$，其中 $0 \le x_i \le 70$。暴力验证表明，这个方程刚好可以 cover 所有的不超过 $\binom{71}{4}$ 的整数。然后五个未知数就是一个经典套路，中途相遇就好了。

ultmaster: 这个题做法大概很多，假做法大概更多。一上来看到这题，智障的某人以为是签到。

Problem F

Upsolved by ultmaster.

题意：定义一个集合的 mindiff 是相邻元素差的最小值，maxdiff 是最大减最小。求 $1$ 到 $n$ 所有子集的 mindiff * maxdiff 之和。

题解：枚举 $d$，令 $\text{mindiff } \ge d$，然后枚举集合中的元素个数 $k$（这两层枚举保证了时间复杂度是 $O(n \log n)$），我们要计算这些集合的 maxdiff 之和。由插板法，先把相邻元素间的多余的元素拿掉，于是令 $m = n - (k-1)(d-1)$。拿掉了这些元素后，等于把原集合缩紧了，maxdiff 就变成了 $\sum_{t=k-1}^{m-1} t(n-t) \binom{t-1}{k-2} = \frac{(m+1)!}{k(k+1)(m-k)!(k-2)!}$。另外 maxdiff 还要把原来的那些拿掉的部分给加上，总共 $\binom{m}{k}$ 个集合，每个集合损失了 $(k-1)(d-1)$。然后做一次差分就可以求出 mindiff 恰好是 $d$ 的 maxdiff 之和。求下点积即可。

Problem H

Unsolved. (-2)

Problem I

Upsolved by zerol. (-13)

题意：求树上的点集个数使得其直径（相距最远的两个点之间的距离）为 D。

题解：直径不唯一，但直径的中点唯一。设枚举的直径中点为 u，设距离 u 小于等于 D 的点数是 a，小于 D 的是 b，每个方向的距离恰好为 D 的是 $c_v$，那么贡献是 $2^a-2^b-2^b \sum_v 2^{c_v}$。距离每个点距离不超过 k 的点的个数可以用点分治做。先当有根树，u 每个儿子遍历前后增加的深度为 dep[u]+D 的点的个数也很容易统计，从 u 上面过来的个数就是 (a-b-\sum_v c_v)。

Problem J

Solved by kblack. 01:38 (+2)

题意：求一个 $1000^2$ 的字母矩阵里类数独矩阵（每行每列的元素各不相同）的数量。

题解：大小写一共52个，预处理向上向左最大距离，枚举右下角/上下边界，可以很轻松的做到 $52n^2$。