CF1804H Code Lock

牛逼题，但是卡常。

首先显然指针会从密码串第 \(1\) 个位置开始，因此我们需要关心的就是相邻两个位置的值。只需要求出 \(c_{x,y}\) 表示前一个是 \(x\)，后一个是 \(y\) 的个数即可。

考虑一般的按顺序填的状压，总是避免不了顺序的问题，总是与 \(k!\) 有关，我们需要一个合适的计算贡献的方法。

首先考虑 \(k\mid2\) 的情况，我们称第 \(i\) 段为第 \(i\) 个和第 \((i-2+k)\bmod k+1\) 中间那一段。同时考虑 \(1\) 和第 \(\frac{k}{2}+1\) 段的出现次数，可以发现：

• 每一对 \(x,y\) 至多经过这两段总共一次。
• 当 \(x,y\) 位于两端同一侧的时候，不会经过这两段，否则会经过这两段恰好一次。因为我们计算的是总和，所以不需要考虑到底经过了具体哪一段。

那么这个问题就变得简单起来了，我们只需要知道 \(\frac{k}{2}\) 段这样的中间有什么即可。枚举第 \(1\) 段和第 \(\frac{k}{2}+1\) 段中间的集合是 \(V\)，然后设 \(f_{S}\) 表示当前滑动窗口的 \(\frac{k}{2}\) 中是什么，每次选出一个在 \(V\) 中并且仍然在 \(S\) 中的扔掉，再选一个不在 \(V\) 中也不在 \(x\) 中的加进来，计算贡献即可。这样的复杂度是 \(O(k^2{k\choose \frac{k}{2}}^2)\)，过不去。

如果能优化掉一个 \(k\) 就好了！发现两步其实是独立的，因此可以先转移一边，再转移另外一边，复杂度就变成 \(O(k{k\choose \frac{k}{2}}^2)\) 了。

对于 \(k\nmid 2\) 的情况，只需要计算所有左端点往后 \(\frac{k}{2}\) 滑动窗口的贡献，然后除以二就是答案了。

有点卡常，强制 \(1\) 在第一段和第 \(\frac{k}{2}+1\) 中间可以将常数变成 \(\frac{1}{2}\)。

submission