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]$。

题解：将 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} $

然后递归求解。

Problem C

Upsolved by zerol.

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 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}$，然后搞一搞。