一些常见错误算法的卡法
CF Hackers 看过来。毒瘤出题人看过来。
主要记录一些常用但是可以被卡的算法的卡法。由于作者太菜了，目前内容很少，欢迎大家私信补充。
字符串哈希
由于 cz 的帖子，现在哈希的卡法已经大众化了……
单哈希、ull 自然溢出、base 为常数但不给出
用 Thue Morse 序列。
证明过程直接照搬巨佬的题解，讲得很详细：
对于二进制串
s ，定义\bar s 为按位翻转后的串。令0 阶 Thue Morse 序列t_0=\texttt{0} ，t_n=t_{n-1}+\overline{t_{n-1}} ，有\text{hash}(t_n)=b^{2^{n-1}}\text{hash}(t_{n-1})+\text{hash}(\overline{t_{n-1}}) ，\text{hash}(\overline{t_n})=b^{2^{n-1}}\text{hash}(\overline{t_{n-1}})+\text{hash}(t_{n-1}) ，记h_n=\text{hash}(t_n)-\text{hash}(\overline{t_n}) ，有h_n=(b^{2^{n-1}}-1)h_{n-1} 。由于
b^{2^{n-1}}-1=(b-1)(b^{2^{n-2}}+1)(b^{2^{n-3}}+1)\dots(b+1) ，而b 是奇数，那么每一项都是偶数，故2^n|b^{2^{n-1}}-1 ，那么2^{\frac{n(n+1)}{2}}|f_n ，对于n\ge11 ，\dfrac{n(n+1)}{2}>64 ，自然溢出就爆炸了。那么输出长度为
2^{11} 的 Thue Morse 序列即可。
个人认为这个卡法很有趣，同时需要数学知识与构造能力。
单哈希、mod 在 int 范围内且给出、base 为常数且给出/不给出
给不给出 base 卡法都一样。
根据生日悖论，对于模数
双哈希、两个 mod 和两个 base 均给出
先随机求出符合前一组哈希的字符串，再以他们为字符集，求出满足第二组哈希的字符串即可。
unordered_set/map
本质上是卡哈希表。
orz 大神的博客。
经过查阅官方文档，C++ 官方哈希函数就是对值做一次哈希，再取一次模。所以只要疯狂往里面塞这些质数的倍数就能不停制造哈希冲突，从而把时间复杂度打到
SPFA
众所周知，关于 SPFA，___。
以下摘自知乎：
朴素 SPFA
- 对于允许负权边的情况，直接链套菊花。弄一条负权链，链上每个点都指向菊花图的支配点，那么菊花图就会不停地被更新。取链上和菊花上节点数均为
\dfrac{n}{2} ，时间复杂度即为\Theta(n^2) 。 - 不允许负权边，用网格图。这张图存在一堆次短路，导致 SPFA 极其容易走错。参考从别人那找来的图：
SLF 优化
- 优化：每次将入队结点距离和队首比较，如果更大则插入至队尾。
- 卡法：还是链套菊花，在链上用几个并列的小边权边就能让算法多次进入菊花。
SLF 带容错
- 优化：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。
- 卡法：在卡 SLF 的基础上开大边权。
LLL 优化
- 优化：每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾。
- 卡法：向
1 连接一条权值巨大的边，这样 LLL 就失效了。？？？优化
- 优化：在第
[L,R] 次访问一个结点时，将其放入队首，否则放入队尾。通常取L=2,R=\sqrt{V} 。 - 卡法：菊花即可。
SLF + swap
- 优化：每当队列改变时，如果队首距离大于队尾，则交换首尾。
- 卡法：与卡 SLF 类似，外挂诱导节点即可。
珂朵莉树
其实非常好卡……
珂朵莉树复杂度的关键是推平操作，这样才能合并节点。那只要没有推平操作珂朵莉树就炸了……