文章
215
标签
0
分类
1
主页
分类
标签
归档
友链
爱飞鱼的blog
cdq分治
搜索
主页
分类
标签
归档
友链
cdq分治
发表于
2023-02-19
|
更新于
2025-03-04
|
ICPC
|
浏览量:
title: cdq分治
categories:
- ICPC
tags:
- null
abbrlink: b55b4eb8
date: 2023-02-19 00:00:00
cdq分治
文章作者:
WTY
文章链接:
https://my-mathmaster-github-io.vercel.app/posts/b55b4eb8.html
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
爱飞鱼的blog
！
上一篇
树哈希
title: 树哈希categories: - ICPCtags: - nullabbrlink: d32ec61edate: 2023-02-16 00:00:00树哈希 一种好写且卡不掉的树哈希考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是$ v_1, v_2, \cdots, v_k$，定义子树的哈希 $h(a)=1+\sum_{1\le i\le k} f(h(v_i))$。其中$h(v_i)$ 是 $v_i$对应子树的哈希，$f$ 为一个待定函数。 可以证明：如果 $f$ 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 $O(n^2/2^w)$。只需考虑最深的一对冲突点即可。 上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。 实践中，我们并不能取一个真正的随机函数当 $f$。但事实上，没有特殊性质的 $f$ 几乎都卡不掉；因为随便找个 $f$ 大概率很随机。 有一些反例：如果 $f$ 取多项式，可能因为一直保持 $2^k$...
下一篇
字符串border系列学习笔记
title: 字符串border系列学习笔记categories: - ICPCtags: - nullabbrlink: aff110d8date: 2023-02-22 00:00:00一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为$1base$ Border:若字符串S的$prefix[i]=suffix[i]$，则称这个前缀或者这个后缀是一个border 周期：对于字符串S，存在整数P满足$S[i]=S[i-P]$$(p<i \le |S| )$,则P为字符串S的一个周期。这里的周期也常被称为循环覆盖。 循环节：若字符串S的周期P满足$p,|, s.size()$,则P是S的一个循环节。 理解：周期用循环覆盖理解，就是长度P的周期拼接若干次以后，S一定作为这其中的子串出现。对于循环节来说，循环节拼接若干次以后，恰好能够得到S。 性质： P是S的周期$\Leftrightarrow...
WTY
理性思考，和平交流
文章
215
标签
0
分类
1
Follow Me
目录
1.
title: cdq分治categories: - ICPCtags: - nullabbrlink: b55b4eb8date: 2023-02-19 00:00:00
cdq分治
最新文章
贪心
2024-12-22
Z_exkmp
2024-12-21
Codeforces Round 895 (Div. 3)
2024-12-16
可持久化字典树（Trie）
2024-12-16
网格图上问题
2024-12-15
搜索
数据加载中
