原题 + 暴力场
汗流浃背了
A
此事在 240729.md 中亦有记载
/** * 设 f[i][x] 表示 i 时刻 x 点的期望贡献 * 小刻都会的转移方程: * f[i + 1][y] += f[i][x] * Pow(Out[x], mod - 2); * 然后 t[i] 时刻 v[i] 点的答案 ++ * f[i] 由 f[i - 1] 转移而来, 转移过程可以看作矩阵乘法 * 所以只求 E[T] 的话矩阵快速幂已经做完了 * 但是现在求 E[1] 到 E[T] 的异或和 * * 注意到求向量乘矩阵的某一项的时间复杂度是 O(n) 的 * 考虑把 T 分成若干长为 B 的块, 每 B 个数处理一次 * 预处理转移矩阵的 1~B 次方, 然后算每个块的首项 * 这个块里 E[i] 就可以 O(n) 算了 */
B
此事在 犇犇 中亦有记载
|| @KinNa_Sky : https://www.luogu.com.cn/record/197272108 O(n^2) 很神奇吧
题见上述提交链接
\(O(n^2)\)
考虑一个等差数列只需知道其中两项即可知道全部。
考虑对于一个询问，首先特判本身已知。
其次只需考虑其所在段能否凑出两个已知项，如果凑不出，再去递归处理左右两个端点是否可以知道。
注意到上述过程最坏 \(O(n^2)\) 但是可以通过。
有老哥讲了一种 \(O(n \log n)\)，虽然没有实现但是写一下。
注意到复杂度主要在处理边缘的项是否可知，把段分成有至少两个的，有一个且非端点的，有一个且在端点的几类。
第一类是我们的目标，第二个考虑如果一个端点已知，那么可以推知另一端点，所以这个可以看成跳边，第三类是断路。
所以这个用什么维护一下就可以加速跳端点。
C
一个小样例：
3 3
1 3
2 1
1 1
1 2
3 1
1 2
对应的数列：
1 1 1 2 1
1 1 3 1 1
这个相比正常 LCS 关键的不同在于一个点可以匹配多个点，甚至多个点可以匹配多个点。
因为多点对多点，所以暴力 \(O(n^4)\) 转移是
\(\displaystyle f_{i, j} = \max_{i' \in [1, i], j'\in [1, j]}\{f_{i' - 1, j' - 1}, \min(suma_{a_i, i} - suma_{a_i, i' - 1}, sumb_{b_j, j} - sumb_{b_j, j' - 1})\}\ (a_i = b_j)\)
\(sum_{i, j}\) 是对应序列的元素 \(i\) 的前缀和。
优化这个过程，\(i', j'\) 往前跳，每次跳 \(sum\) 较小的指针，跳到上一次 \(a_i\) 出现的位置（因为这之间的转移权值是不变的，而 dp 值在转移权值相同时在 \(i', j'\) 最大时最大）。
小常熟 \(O(n^3)\) 在集训 OJ 上卡过了。
题解 \(O(n^2 \log^2 n)\)
上述式子令 \(i' - 1 \to i',j' - 1 \to j', a_i \to x,b_j \to x\)。
\(\displaystyle f_{i, j} = \max_{i' \in [1, i), j'\in [1, j)}\{f_{i', j'}, \min(suma_{x, i} - suma_{x, i'}, sumb_{x, j} - sumb_{x, j'})\}\)
不妨设 \(suma_{x, i} - suma_{x, i'} \le sumb_{x, j} - sumb_{x, j'}\)。即 \(suma_{x, i} - sumb_{x, j} \le suma_{x, i'} - sumb_{x, j'}\)。
三维数点。