1.24 模拟赛

A Power

看到这题数据随机就可以想到可不可以乱搞。我们考虑从 $P-1$ 开始向下枚举,每次用 BSGS 解出这个数第一次出现的位置,如果这个数小于之前的最小位置,我们就用它来代替最小位置继续做。然后考虑设置一个阈值 $B$ ,如果当前的数已经小于了 $B$ 就停止这个做法直接枚举前 $B$ 个数。

然后写出来试了试发现只能过 $10^7$ 。冷静分析一波复杂度,会发现如果 $B$ 控制合理大概是 $O(P^{\frac 3 4})$ 的东西。具体来说,随机情况下如果我们找到了一个比当前最优位置小的位置,就期望可以让最小值减半。而出现这种数的时候大概是一个线段树的结构,我们可以认为出现这种数的概率是 $\frac1 {2^k}$ 这种东西。总的来说,期望可以用 $O(\frac P B T)$ ,其中 $T$ 是 BSGS 查询一次的复杂度,来让规模减小到 $B$ ,最后暴力复杂度是 $O(B)$ 。然后发现如果优秀地调整 BSGS 块的大小复杂度是 $O(P^{\frac 2 3})$ ,但是还是常数太大。然后考虑减枝,也就是在 BSGS 的时候如果当前都已经大于最小值就不管了,这些优化都加上后,会发现可以过 60 分,本机跑极限数据也只需要 1.6s~1.9s 可惜 OJ 太慢过不去。

如何做优化?我们考虑把 $x$ 写成 $\omega^t$ 的形式,其中 $\omega$ 是原根。于是就变成了解 $\omega^{kt} = \omega^a$ 这种东西。但是如果我们想用 BSGS 算 $\omega^a$ 的 $a$ 那复杂度还是没变。但是可以发现如果阈值是 $10^6$ 级别,最多就只会用到 $[P-5000,P-1]$ 这个范围,我们可以预处理出它们的 $a$ 。然后就变成了解 $kt \equiv a \pmod {P-1}$ 的形式,这可以用扩欧解决。相当于我们就把上面 BSGS 的复杂度变成了一次扩展欧几里得的复杂度。

B Match

这题以前见过超级弱化版:CF808G。但是如果没了 $nm \le 10^7$ 就很难顶。

我们还是先考虑 $O(nm)$ 的做法。

考虑设 $dp[i]$ 表示匹配了 $1 \sim i$ ,最后一个匹配结束位置钦定为 $i$ ,最优的答案。于是 $dp[i]$ 有值当且仅当 $S[i-m+1,i]$ 和 $T[1,m]$ 可以匹配(算了通配符)。

转移有两种,一种是 $dp[i] = \max\{dp[i],f[i-m]\}$ 其中 $f[i] = \max_{k \le i} dp[k]$ ,也就是直接在这里新作为一个串,与之前没有重叠。这种可以直接 $O(1)$ 转移。还有一种:

就是枚举一个 $\text{border}$ 然后从它前缀结束位置后面再加字符。

但是众所周知,$\text{border}$ 的个数是 $O(m)$ 的,直接转移复杂度 $O(nm)$ 。

然后有这么一个结论:一个串的 $\text{border}$ 一定可以划分成 $O(\log(n))$ 个等差数列。这类似于回文里面的 $\text{border}$ 定理。结论证明大概是讨论一个串的 $\text{border}$ 是否小于串长除以二,如果大于,那么可以证明在经过等差数列的很多个 $\text{border}$ 后可以得到一个不到 $\frac m 2$ 的 $\text{border}$ 。

于是我们对每个等差数列开公差个 set ,每个 set 里面存仍然可用的,模公差等于某个值的所有下标里面的东西。然后每次枚举到下一个字符的时候维护这个 set 即可。其实可能也可以用单调队列维护。这题 $n,m \le 10^5$ ,怎么写都能过。

然后还有个问题就是带通配符的字符串匹配。这个可以用一个 NTT 解决。具体来说,大概就是

这个玩意,然后给通配符的位置置为 $0$ 。

复杂度 $O(n\log^2 n)$ 。

后来学习了一下别人的实现。发现其实没有必要对每个等差数列开 set 。std 中是直接把 set 换成了单调队列。但是 qty 代码中考虑了其实 $\max$ 这个东西可以允许重复计数,所以我们可以对每个公差直接记录一个值,表示到当前为止模公差等于某个值的时候最大的 $dp$ 值。因为如果在 $i - m$ 之前的 $dp$ 值转移过来,即使优秀它也属于合法的转移。所以类似 qty 代码中可以直接对每个等差数列开一个数组 f[MAXN] ,$f[i]$ 表示 $\max_{j < i , j \equiv i \pmod d} dp[j]$ 。这样就可以直接从 $f[i - d]$ 转移过来。会非常好写,复杂度也是 $O(n\log n)$ ,优于 set

C Tile

神仙题。

考虑放入俄罗斯方块的过程。为了满足题目中给的条件,它必然是随时维护着一个上轮廓线。于是放入一个方块有这么几种情况:

image.png

考虑它对轮廓线的影响,会发现一定是两边从 U R 变成了 R U ,然后中间不变,并且对于任意一种中间两个位置,都有一种方块与之对应。

于是我们考虑给轮廓线按 $\bmod 3$ 来分类处理。如果分类后,相当于是每一轮可以给相邻的 U R 变成 R U 这东西。由于 $\bmod 3$ 后互不影响,最后给三类乘起来做一个可重排列即可。

考虑模三后的每个东西,每次操作相当于

image.png

也就是往轮廓线里填一个数。如果我们按照填入时间来给每个格子填数,那会变成一个杨表的计数。杨表计数是一个叫做钩子公式的东西。具体来说是

定义 $\text{hook}[i,j]$ 表示 $[i,j]$ 这格子以及它上面的,左边的格子的个数。

于是我们对每个对角线分别计算即可。复杂度 $O(nm + T(n+m))$ 。

文章作者: yijan
文章链接: https://yijan.co/2021/02/13/124-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog