tips
先考虑不去掉 $k$，由求和子集的对称性很容易猜想答案就是 $0$。如何证明？利用对称性。\(S=\{1,2,\dots,p-1\}\)，试着找到一个双射 \(f:S\to S\)，可以知道在 \(f\) 的映射下答案是不变的。
我们可以找原根。设 \(g\) 是 \(p\) 的一个原根，\(\{1,2,\dots,p-1\} = \{g,2g,\dots,(p-1)g\}\)。
然后再考虑答案。若前面的集合答案是 \(x\)，后面的就是 \(xg^t\)。相等可知 \(x=0\)。关于 \(t\) 的大小可能需要讨论讨论。
最后建立递推式即可求得最终答案。
tips
整体考虑一次操作对数列的改变。这会使数列多一个数并且数列的和会增加 $k$。如果 \(k\) 为 \(0\)，操作带来的改变就简单许多，仅仅多一个数而总和是不变的。此时的答案很容易讨论得出。提示：考虑终局下每一个相同的数是被谁生成出来的。
若 \(k\) 不为 \(0\)，数列的总和就取决于操作的次数，讨论起来较复杂。如何让这个和不随操作数变化？
考虑式子 \(x+k=y+z\)，有一定对称性。两边同时减掉 \(2k\) 得 \(x-k=(y-k)+(z-k)\)，这提示我们 \(k\) 在每一次操作的影响可以在所有操作开始之前算清。也就是说，如果在最开始我们把所有数都减掉 \(k\)，那么之后的操作，\(k\) 不再影响总和。
tips
如果求的是路径数？矩阵快速幂板题！现在变成长度最值，只要将矩阵乘法的两个运算 + * 替换为 min(max) + 即可，易证满足结合律。
tips
tip1
先考虑求某个 $\mathrm{W}(S_i)$。一个显然的贪心是如果当前最小值大过 $k$，直接用操作二，小于 $k$ 用操作一，一定不劣。接下来我们要考虑的可能是讨论往现在的集合加（或者删）一个数会对答案产生怎样的变化。
为了研究这个变化，我们需要获得比原来的贪心更多的信息，考虑把原来的贪心写成 dp。
tip2
倒着 d，$f_i$ 表示总共已经减掉 $i$ 了的情况下，还需要至少多少次才能清空集合。每次从 \(i+k\) 以及 比 \(i\) 大的下一个在集合中的数 这两个点转移。考虑到 \(f\) 的单调性，其实就是找下标更大的 \(f\) 转移过来。
怎么处理新加点带来的改变？
tip3
如果强行讨论，确实可以发现一些能算作规律的东西......这个过程中你会发现改变了的 $f$ 是很多段，不好直接处理。“比 \(i\) 大的下一个在集合中的数”这个转移有点不常规，试着修改一下。想想我们先前的贪心。
tip4
什么时候用操作一？只有在某个集合中的点左边长度为 $k$ 的范围内的那些 $f$，才会用这个转移，其余情况下都是用的操作二。也就是说，选择第二个转移的 $f$ 也是一段一段的，而且一个很好的性质是这里的每一段都是从一个 $f$ 转移来的。再考虑不断加点的过程中，某一个特定的 \(f_i\) 转移取舍的变化。在前一段时间里，这个 \(f_i\) 使用的是转移二，是从一个右边的很远的点转移过来的。新加点的时候，可能转移二的转移点更靠近了，但离这个 \(f_i\) 的距离还是大于 \(k\)。在这段时间内，虽然 \(f_i\) 的转移点变化了，但选择的是转移二没有变，也就是说，它还是和 \(f_{i+1}\) 的转移点一致。这提示我们，这段时间内我们只需要让 \(f_i\) 从 \(f_{i+1}\) 转移过来即可。而当新加点在 \(i+k\) 以内后，\(f_i\) 将永远从 \(i+k\) 转移过来。
我们得到一个惊人的结论，在某一个时刻，所有的 \(f\) 只会选择唯一一个点进行转移。我们成功地把转移的结构变成了一棵树。LCT 即可。
也可使用根号重构的 trick 避免 LCT。