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)$ 转移。还有一种：

$dp[i] = \max_{b \in \text{border}}\{dp[i-m+b]\} + 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 解决。具体来说，大概就是

$\sum_{i-j = k} S[i](S[i] - T[j])^2$

这个玩意，然后给通配符的位置置为 $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

神仙题。

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

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

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

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

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

$\frac{n!}{\prod \text{hook[i,j]}!}$

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

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