专栏文章
树哈希
算法·理论参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqhyv19
- 此快照首次捕获于
- 2025/12/04 05:06 3 个月前
- 此快照最后确认于
- 2025/12/04 05:06 3 个月前
定义子树的 hash 值为：
其中 是一个随机函数。
“可以证明：如果 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 。”
“上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。”
CPPinline ull H_value(ull x) {
return x*x*x*1237123+1000010101;
}
inline ull gf(ull x) {
return H_value(x&((1ull<<31)-1))+H_value(x>>31);
}
1000010101 是质数耶。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...