P10158 题解

· · 题解

随机化做法，欢迎 Hack．

只有 1、3、4 操作的情况过于简单，这里不再过多讲述．

考虑 2 操作中对于 [l,r] 的命题是真命题的一个必要条件：

\sum_{i=l+k}^r a_j \equiv \sum_{i=l+k}^r \sum_{j=i-k}^{i-1} a_j \pmod p.

同余号两边的式子均可以通过线段树维护区间和及区间编号乘权值和的方式快速得出．

注意到这个条件并不充分．考虑随机化．约定常数 D，每次 2 操作时，把 [l+k,r] 区间划分成 D 个互不相交的子区间，然后分别进行上述必要条件的检验．若所有子区间均通过检验，则认为原命题成立．

发现有一种简单的构造可 Hack 上述做法：另每次 2 操作 k=1，且 [l,r] 区间内只有一个数和其他数不同．此时若这个不同的数字没有单独被划分到一个区间内，则上述做法会得到错误的结果．考虑通过特判 k=1 的方式来规避该 Hack．

在 k>1 的情况下，笔者尝试过多种方式，均无法 Hack 掉该做法．欢迎各位读者尝试 Hack．

经测试取 D=8 时可以稳定通过本题目前的所有数据．

代码参考见 外部剪贴板．