AT_abc367 补题报告【G】

zhangjinxuan

前言

我感觉我写这些内容对自己有很大益处，尤其是考试补题，因为补题不仅仅是一个“能多几个 AC”的作用，还是一个吸取教训、总结、提升自己的一个重要途径。从某种意义上来说这是写给自己的。

每一场（方便公开）的比赛如果改完题目（达到能力上限）就会来总结。由于 lz 水平有限，所以一些帖子的学术性问题欢迎在本贴讨论指出错误。

---

比赛题目：https://atcoder.jp/contests/abc367/tasks

问题 D

一个湖周围有 $N$ 个休息区。  
这些休息区按顺时针顺序编号为 $1$ 、 $2$ 、......、 $N$ 。  
从休息区 $i$ 顺时针走到休息区 $i+1$ 需要 $A_i$ 步（其中休息区 $N+1$ 指的是休息区 $1$ ）。  
从休息区 $s$ 顺时针步行至休息区 $t$ 所需的最小步数（ $s \neq t$ ）。是 $M$ 的倍数。  
求 $(s,t)$ 可能的对数。

针对于这种循环的序列，可以将原序列拓展一份，然后问题就转换成了（转换问题才是问题最难点，尤其是 +1 -1 这种猎奇），原序列对于所有 $i\ge n$ 的位置，满足 $\sum_{k=j}^{i} A_k \equiv 0 \pmod M$ 的 $j$ 的总数，且 $j\ge i-n+1$。

显然先对 $A$ 做一遍前缀和，那么就是相等的位置的总数了，可以用桶维护。再使用类似于滑动窗口的技巧，对于一个位置如果是大于 $\ge n$ 的，那么就消除掉 $i-n$ 的影响，这样就能维护所选择区间长度为 $N$ 的性质了。

赛后：https://atcoder.jp/contests/abc367/submissions/56836246


问题 E

给定长度为 $N$ 的序列 $X$ 和 $A$，进行 $K$ 次操作：
- 令序列 $B$ 满足 $B_i = A_{X_i}$，再把 $A$ 替换。
输出序列 $A$。

如果把序列拆开，单点考虑，也就是对于每一个位置 $i$ 进行 $K$ 次操作，即令 $B=X_i$，再将 $i=B$，求最后的 $A_i$。

于是你就发现变成了一道 FCOI #3 的最后一道题 /jk，倍增板子。

场切：https://atcoder.jp/contests/abc367/submissions/56830410

问题 F

无序集合哈希板子，即判断分别从两个序列中截取出来的区间所组成的无序集合是否相同。

无序集合哈希就是把集合中的每一个元素的哈希值通过具有交换律的运算运算再一起所得到的结果就是这个集合的哈希。

容易发现我们需要设计两个哈希函数，一个是针对于值的 $f_1$，一个是针对于集合的 $f_2$。

那么就要想应该怎么做才能让正确率高了，其中一个常见的做法就是把 $f_1$ 设计为一个多次的多项式（次数越多越好），可以取模，然后 $f_2$ 设计为加或者是异或。

我使用的是 $f_1(x) = x^5$，$f_2(S) = \sum_{x\in S} x$。集合哈希和正常的哈希一样，也是可以双哈的。

场切：https://atcoder.jp/contests/abc367/submissions/56822504


问题 G

好像超纲了，说是什么 hadamard 变换，暂时不会。

总结教训

问题简单化，能拆就拆。

还有就是自己出的题不要自己搞忘 \jk。

陈尚涵

大佬ORZ%%%