0210 模拟题解

0210 模拟题解

t1

直接枚举 \(k\)，考虑计算答案。

首先发现这个限制等价于存在长度 \(\ge n-k\) 的上升子段。

那我们反过来，计算所有上升子段长度都 \(\le n-k-1\) 的方案数。

把序列划分成若干极大上升子段的方案是唯一的，下面直接称为子段。

令 \(t=n-k-1\)。

令 \(dp_i\) 表示考虑了前 \(i\) 位的方案数。

转移先是有 \(dp_{i}=dp_{i-1}\times i\)，表示第 \(i\) 位随便放。

然后发现这么弄出来可能会存在长度恰好 \(=t+1\) 的子段，需要减去。

我们直接减去 \(dp_{i-t-1}\)，意思是前面 \(i-t-1\) 随便放，然后 \(t+1\) 个上升。

这样减掉了末尾长度为 \(t+1,t+2,...,2t\) 的方案。

再加上 \(dp_{i-t-2}\)，这样多算了末尾长度为 \(2t+1\) 的方案。

发现和上面问题是一样的形式，继续这么容斥，直到 \(dp_{i-xt-1}\) 为 \(0\)。

时间复杂度：\(O(n^2\ln n)\)

空间复杂度：\(O(n)\)

t2

随机数据，所以可以考虑一些乱搞的做法。

先暴力跑前若干次，我写的时候选的是 \(8\times 10^5\)，这样前缀 \(\max\) 就会比较大。

然后对于剩下的 \([\max+1,P-1]\)，对每个都暴力解出第一次出现的位置然后算贡献。

相当于要解 \(a^x=b\)，可以用 \(\text{BSGS}\) 解决。

但是 \(\text{BSGS}\) 需要调块长，然后发现预处理复杂度和查询复杂度不管怎么调都过不去。

因为要预处理 \(200\) 次，如果只要预处理 \(1\) 次就能把预处理的长度变得更大。

可以利用原根。

原根可以满足对于任意 \(a\in[1,P-1]\) 都存在 \(x\)，使得 \(g^x=a\)。

方程变成 \(g^{cx}=g^{d}\pmod {P}\)，可以用 \(\text{exgcd}\) 解决。

时间复杂度：\(O(能过)\)。

t3

可以想到一个 \(dp\)，转移的时候发现需要满足形如 \(t\) 有长度为 \(L\) 的 \(\text{border}\) 的限制。

而且能转移也必须要满足 \(s\) 在存在通配符的情况下某个子段能和 \(t\) 匹配。

通配匹配只能通过 \(\text{FFT/bitset}\) 解决。

\(\text{border}\) 太多了，转移太慢了，怎么办？

有个经典结论是字符串 \(s\) 的所有 \(\text{border}\) 可以拆分成 \(O(\log)\) 个等差数列。

因此每个等差数列可以用单调队列维护。

时间复杂度：\(O(n\log n+\frac{n^2}w)\) 或 \(O(n\log n+|\Sigma|n\log n)\)。