一个适合换根树哈希函数
一个适合换根树哈希函数
本文搬运自本人高中时期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...
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]...
2022-01-16
【P6739 [BalticOI 2014 Day1] Three Friends】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15809039.html 题目链接 题目 有一个字符串 SSS，对他进行操作： 将 SSS 复制为两份，存在字符串 TTT 中 在 TTT 的某一位置上插入一个字符，得到字符串 UUU 现在给定 UUU，求 SSS。 思路 哈希 先预处理这个字符串的哈希前缀和，然后枚举插入位置，这时候把左右的 SSS 求出来，看看是否相同。 需要注意的是，题目是说 SSS 不是唯一的猜输出 NOT UNIQUE，也就是说如果有多种切断方式但 SSS 一样还是...
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// ...
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...