1.24 模拟赛

A Power

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

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

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

B Match

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

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

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

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

dp[i]=maxbborder{dp[im+b]}+1dp[i] = \max_{b \in \text{border}}\{dp[i-m+b]\} + 1

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

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

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

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

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

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

这个玩意,然后给通配符的位置置为 00

复杂度 O(nlog2n)O(n\log^2 n)

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

C Tile

神仙题。

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

image.png

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

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

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

image.png

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

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

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

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

\