P9753 消消乐题解

不知道算不算题解。

大概是一些零散的想法。

首先一个观察就是，用栈从左侧往右扫描。然后你发现栈内元素一样说明这两个点的区间就是可以消除的。

因此你可以对栈哈希。哈希可以直接考虑数组哈希的做法，对于第 位乘上一个大质数的 次幂在加起来。用栈可以维护到栈顶为止的哈希值，每次 push 就是栈顶的值加上当前值乘上 。

不过，这个东西还是太难发现了。

我们不妨换个角度。

简而言之，你从左往右做操作，相邻两个操作抵消。这意味着 。并且，我们不能随意交换两个元素，交换律在这里并不成立。

如果你熟悉线性代数，很快就会发现这可以是一个镜面反射。因此我们可以用一个镜面反射的矩阵代替每个字符 。可以在前面复合上前缀的逆元来获取一段值的哈希值（这其实是哈希的性质）。

此外这还依赖一个性质就是结合律。假设有 拼接起来消除，和 分别消除拼接起来再消除是一样的。

这也是我们可以使用矩阵的原因，有结合律，但是我们需要消除交换。

此外还有一个满足条件的哈希，那就是对换。你可以使用对换来代表每个元素。你只需要 个元素即可。

维护这个东西的做法是直接维护整个置换，然后对置换做数组哈希。

对于， 并且有交换律的情况，可以考虑异或哈希。

或者采用比较笨的办法，用 字符串表示是否出现过。然后对字符串做哈希。本质还是数组哈希。（我们数组哈希真的是太有用了！）

总结一下就是，哈希的作用是快速判等（这里的等指的是等价关系，并非狭义的相等），前提是可以设计哈希函数使得同一个等价类的哈希值相同。

此外顺手记录一下之前听到另一个有趣的应用，就是校验码。考察银行卡号，在卡号最后增加一位，使得可以检验银行卡号是否合法，减少转账录错银行卡号转给了错误的人这种事情发生的概率。

其似乎仍然是把所有银行卡划分成若干等价类，选择一个等价类，称这个等价类是合法的银行卡号。一个简单方法就是在最后加上一位作为校验码。

请注意我们此时的要求。不满足交换律，可以有结合律（因为字符串拼接有结合律）。并且要能检测某一位出错的情况，且校验码要在 之间。

最后一个要求让直接字符串哈希不太可能了。一个有趣的解法是，将 映射二面体群 中的一个元素，最后添加校验码使得所有元素复合起来是 。

似乎有一个人设计了将 映射到某个具体的 中的元素取得的比较优的效果。

不过似乎并没有银行采取这种方法。

此外还有集合哈希。集合哈希更好的做法其实并不是直接对 01 字符串做哈希，此类哈希函数很难写，并且缺乏良好的性质。我们有着更好的哈希方式。考虑给每个元素随机权值，定义集合的哈希值就是所有元素乘积相乘。

这样做的更好的方法是可以很好的对集合族做哈希，定义集合族的哈希为所有集合的哈希相加。如果要给一个集合族所有个数添加一个元素，那么只需要哈希值乘上一个数即可。

这个做法的本质就是若干 的乘积，表示第 个元素选或不选。其碰撞概率有 Schwartz-Zippel 保证。