一个适合换根树哈希函数
一个适合换根树哈希函数
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133146153
这个方法适用于对整棵树统计每个节点的哈希值，也适合换根（因为只和他的儿子节点集合有关）
当然，写双哈希是最稳妥的
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-21
树哈希与换根DP：CF763D
树哈希与换根dp：CF763D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133148959 采用的树哈希函数是： dpx=wx×∑y∈xdpy2+wx2\Large dp_x=w_x\times \sum_{y\in x}dp_y^2+w_x^2 dpx=wx×y∈x∑dpy2+wx2 发现从 xxx 到 yyy 时只有 xxx 与 yyy 的哈希值会变化，分别维护即可 12345678910111213141516171819202122...
2023-11-13
兔队线段树维护后缀非严格递增子序列的哈希值：CCPC2023深圳K
兔队线段树维护后缀非严格递增子序列的哈希值：CCPC2023深圳K 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134372798 https://vjudge.net/contest/594134#problem/K 场上想到如果两个序列的后缀非严格递增子序列相同则平局，但不知道怎么维护 发现不用输出谁赢，只用判断是否平局，所以肯定是判断两个东西是否相等 然后如果单纯维护后缀非严格递增子序列，可以直接兔队线段树 O(nlog2n)O(n\log^2n...
2021-11-15
【洛谷P1379 八数码难题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558545.html 题目链接 和atc之前的一道题类似，都是暴力广搜+记录状态。 从开始状态开始广搜，然后直接拿个map或者哈希记录状态即可。 时间复杂度为: O(9!)O(9!)O(9!)，因为最多也只有这么多种状态。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// ...
2022-01-16
【P3538 [POI2012]OKR-A Horrible Poem】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15810272.html 题目 原题来自：POI 2012 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。 如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。 思路 首先，我们如果有三点： 一个字符串的循环节必然是字符串长度的约数 循环节的倍数如果长度还是字符串长度的约数，那么他也是循环节 如果一个长度 iii 是字符串循环节长度，那么 [l,r−i][l, r-i]...
2024-08-26
8.26T1 日记和最短路（二分 哈希 倍增）
8.26T1 日记和最短路（二分 哈希 倍增） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575217 http://cplusoj.com/d/senior/p/NOD2301A 题解做法复杂度是错的，hack掉了 比较两个字符串常见方法是二分加hash 在这题套个倍增就行 题解做法也有可取的，把一个串拆成一堆小字符，实现起来方便很多 最后我打了9k 复杂度两只log 123456789101112131415161718192021222324...
2026-08-16
CF2196E：SA的应用
CF2196E：SA的应用 首先贪心的思路是显然的，因此我们相当于在t串中不断求最长可错配lcp 法1：根号分治 我们考虑以 BBB 分块 Case1：对于 d≤Bd\le Bd≤B 的情况。（即一次最多走 ddd 步） 我们可以先预处理 sss 中所有小于等于 BBB 的子串，并枚举它的哪个位置是空的。接下来把这个串挖掉这个空直接丢入hash中（相当于我们枚举的这一位直接赋值为0），这样的复杂度是 O(nB2)O(nB^2)O(nB2) 的。 然后我们现在处理 ttt 串。我们可以枚举每一个被替换的位置 iii ，那么显然 iii 只有 BBB 种可能。然后我们再去枚举 ddd。...