2018 Multi-University, Nowcoder Day 9

Problem A

Solved by zerol. 02:10 (+)

题意：已知 a 和 x 的 FWT 结果是 b，输入 a 和 b，求 x。 求解 $Ax=b \pmod p$，其中 $A_{ij}=a[i \oplus j]$。（n 恰好是 2 的幂）

题解：将 A x b 都分块，A 分成 4 块，其中左上右下以及左下右上完全一样，而且四个子矩阵也有这个性质。

$\begin{pmatrix} A & B \\ B & A \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}$

$\begin{eqnarray}A x_1 + B x_2 = b_1 \\ B x_1 + A x_2 = b_2 \end{eqnarray} $

两式相加减，得到

$\begin{eqnarray} (A+B)(x_1+x_2)=(b_1+b_2) \\ (A-B)(x_1-x_2)=(b_1-b_2) \end{eqnarray} $

然后递归求解。

正解 $x = fwt^{-1}(fwt(b)/fwt(a))$

Problem C

Upsolved by zerol & ultmaster.

题意：用 $2^{2n-1}$ 的钱压 2n-1 场比赛中有至少 n 场赢，赢了得到这么多钱，输了就亏这么多钱。现在只能一场一场压，要求最后能够达到相同的效果。每次先输出压的金额，然后告诉你这场的输赢，然后再决定下一场的金额（如果赢或输达到 n 场，那么立即结束，要求此时输赢的钱数恰好是 $2^{2n-1}$）。

题解：假设我有一张表 a[i][j]（n=i 时，如果一直赢，第 j 场的金额），是 n<k 时如果一直赢/输时的策略。对于 n=k，考虑 赢赢赢输，我要它和 n=k-1 时的 赢赢 等效，然后按照 n=k-1 的策略执行，只是金额扩大 4 倍。这会对这张表提出一些要求，具体就是：设 s 是 a 的每行前缀和，那么要满足 s[i][j] - a[i][j + 1] = s[i][j - 1] * 4。由于知道每行的和是 $2^{2i-1}$，所以这张表能推出来，但是会超时。然后打表找规律，发现和组合数有关。

zerol: 遗憾的是根本就没有考虑 dp 或者输赢的概率。

Problem D

Upsolved by ultmaster.

题意：给一个按照某种规则生成的有关 $n,k$ 的图，求欧拉回路的总数。

题解：运用矩阵树定理和 BEST 定理求欧拉回路数量；然后解出线性递推的关系式即可。

ultmaster: 其实两步都有了，就是没搭上，遂挂机。

Problem E

Solved by kblack. 00:28 (+)

题意：连击奖励 $(Combo)^m$，每个时刻 $p_i$ 概率按对，求期望得分。

题解：$n^2$ 枚举最终连续区间，算一下对得分的期望贡献。

Problem F

Solved by ultmaster. 01:08 (+5)

题意：你在键盘上打字，偶尔还会按按退格键。每次操作之后，问你最少需要敲几次键盘，才能使得给定串中的至少一个作为你当前串的后缀出现。

题解：大概就是建个 AC 自动机，然后反向 BFS 求距离。用个栈维护一下当前状态。

一开始 BFS 写错了。WA1。

改好了 BFS。WA2。

发现其实 0 的边也要加入。遂修复。WA3。通过数据 40%。

突然发现是出现串。我的算法只能判后缀。然后改改改。WA4。40% 变成了 0%。

发现有个地方还是写错了。WA5。20%？

开始怀疑人生，刚才的 40% 呢。。。。咦？难道？AC 之后报了个警。题意遂修改。

Problem G

Upsolved by zerol.

题意：求四个数列的最长公共子序列。前三个数列各自满足相同的数字至多出现两次。

题解：把每个数字在四个数列中的位置的四元组列出来，至多 8n 个，然后就是求四维偏序的 LIS 了。

zerol：用 CDQ×3，CDQ×2+BIT，K-D tree （带重构/带有效标记）都能过。K-D tree 需要剪枝才能过，因为是求 max，所以能剪枝，否则如果是计数题的话就 T 了。

Problem H

Solved by kblack. 01:10 (+)

题意：单点加，求 n 次前缀和。

题解：结合两种暴力，贡献只与距离有关达到查询 $O(M)$ 修改 $O(1)$，暴力一次前缀和达到查询 $O(1)$ 修改 $O(kn)$选个好参数（然后数据可能比较松？）卡了过去。正确方法似乎是推广二维情况的树状数组解法，对 $0 \leq k \leq K$ 维护 $\sum_{i=1}^{x}{i^ka_i}$，然后搞一搞。