2022.7.5考试总结
T1
某个不太正确的方式
想到了分块，暴力没操过去。
考虑暴力计算出前 \(\sqrt P\) 个数的值，期望得到的最大值为 \(P-\sqrt P\)，剩下来的数一定不多，我的想法是分块探测一下下一个块中是否存在比当前最大值更大的数，探测方式是用个 \(\text{hash\_table}\) 记录下每块的每个数的方幂，然后把等式左边乘上逆元后再查找，但是这个做法只有 \(60pts\)，虽然我本机能跑过。
后面想了一下还看了下代码，这个方式的复杂度是错的，因为探测总次数还是不对头。2022.10.7
正常的考虑方式
发现我们对同一个数的探测次数有点多，考虑能不能对一个数只探测一次。本质上是需要求 \(P-1,P-2,\cdots P - \sqrt P\) 这些数在数列中出现的第一个位置。我们的探测实际上是判断了一个幂函数的解是否存在于一个区间。所以直接考虑求解这个幂函数方程 \(x^r = a\)。
考虑 \(BSGS\)，但是需要解 \(T\times \sqrt{P}\) 次，每次的复杂度为 \(O(\sqrt P)\)，不如暴力。
考虑平衡复杂度，设暴力处理的长度为 \(S\)，\(BSGS\) 预处理长度为 \(B\)，那么复杂度为 $T(S+ + B) $
后面那一坨最优应该是 \(3e6\) ，压力山大。
发现质数是同一个质数，有没有什么办法可以优化一下。
答案是，处理离散对数。
离散对数有着和正常对数一样优美的换底公式，如果我们对 \(x,P-1,P-2\cdots P-\sqrt P\)。向 \(P\) 的原根 \(g\)，取对数，那么可以利用换底公式很方便的求解 \(x^r = a\)，取对数的过程就是 \(BSGS\)，注意到换底公式的除法变成了模 \(P-1\) 意义下的除法，因为 \(g^{P-1} = 1\)。
所以 \(BSGS\) 的总次数变为了 \(O(\frac{P}{S})\) 次，预处理只需要一次。这里可以放开玩。
总复杂度变为了 \(O(T*(S+\frac{P}{S})+ B + \frac{P}{S}\times\frac{P}{B})\)
取 \(B = P^{\frac{3}{4}}\)，\(S=\sqrt P\) 可以取到最优。
我实现的时候写的比较丑，算了每个东西的位置之后，还需要排个序，实际上从大到小倒着做就可以了。
看看佳老师的代码，长进不少。
T2
定义字符串的 border 为一个它的前缀，这个前缀也是它的后缀。
场上是只会 \(O(n^2)\) 的，还 TM 暴力打挂了只有 40。
后面了解到可以用 FFT 处理带通配符的字符串匹配问题。
具体的，定义距离函数 \(d_i=\sum\limits_{j=1}^{m} s_{i+j-1}t_i(s_{i+j-1}-t_j)^2\)
显然，如果距离 \(d_i\) 为 \(0\)，那么 \(i\) 开头的字符串就能匹配上。
下标有点问题，所以把 \(t\) 反转一下，把式子拆了，就是三遍 FFT 求出来每一个 \(d_i\)。
我们就知道了哪些结束位置可能可以匹配上。
不是所有能匹配上的位置一定可以对答案贡献，因为如果前面的匹配上了，通配符就没了，所以后面要匹配上，就要求重叠的部分必须是一个 border。
其实 border 在字符串随机的情况下是很少的。我们可以考虑记录下所有的 border，然后 dp，设 dp[i] 表示强制 i 结尾匹配上了，最多能匹配的个数，如果 \(j\leq i-m\)，就是个前缀 max，如果 \(j> i-m\)，就只有 border 能转移。
border 有个性质，就是它们的长度构成 \(\log n\) 个等差数列，所以我们考虑对每个等差数列做转移。
更具体的，如果 \(next[n]>\frac{n}{2}\)，那么模板串一定是一个循环，并且最小循环长度为 \(n-next[n]\)，它的长度大于等于 \(r=n\%(n-next[n])\) 的 border 一定构成一个公差为 \(d=n-next[n]\) 的等差数列。这样的话，\(n\) 每次至少减半，所以至多有 \(\log n\) 个等差数列。
考虑证明。如果存在一个长度大于 \(r\) 的 border \(x\) 长度不能写成 \(kd+r\)，感性理解下，把原串划分为长度为 \(d\) 的小串，把 \(x\) 在末尾的部分平移到开头，显然它还有一个更小的循环。
所以我们对于一个点，含 border 的转移就可以分为 \(\log n\) 类，对每一类记一个前缀 \(\max\) 即可转移，注意每一类需要按照模公差分类。
注意转移细节。
1 |
|