文章
215
标签
3
分类
3
主页
分类
标签
归档
友链
爱飞鱼的blog
cdq分治
搜索
主页
分类
标签
归档
友链
cdq分治
发表于
2023-02-19
|
更新于
2025-08-05
|
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: ICPC tags: null abbrlink: d32ec61e date: 2023-02-16 00:00:00 树哈希 一种好写且卡不掉的树哈希 考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是$ v_1, v_2, \cdots, v_k$，定义子树的哈希 h(a)=1+∑1≤i≤kf(h(vi))h(a)=1+\sum_{1\le i\le k} f(h(v_i))h(a)=1+∑1≤i≤kf(h(vi))。其中h(vi)h(v_i)h(vi) 是 viv_ivi对应子树的哈希，fff 为一个待定函数。 可以证明：如果 fff 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 O(n2/2w)O(n^2/2^w)O(n2/2w)。只需考虑最深的一对冲突点即可。 上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。 实践中，我们并不能取一个真正的随机函数当 fff。但事实上，没有特殊性质的 fff 几乎都卡不掉；因为随便找个 fff...
下一篇
字符串border系列学习笔记
title: 字符串border系列学习笔记 categories: ICPC tags: null abbrlink: aff110d8 date: 2023-02-22 00:00:00 一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为1base1base1base Border:若字符串S的prefix[i]=suffix[i]prefix[i]=suffix[i]prefix[i]=suffix[i]，则称这个前缀或者这个后缀是一个border 周期：对于字符串S，存在整数P满足S[i]=S[i−P]S[i]=S[i-P]S[i]=S[i−P](p<i≤∣S∣)(p<i \le |S| )(p<i≤∣S∣),则P为字符串S的一个周期。这里的周期也常被称为循环覆盖。 循环节：若字符串S的周期P满足p ∣ s.size()p\,|\,...
WTY
理性思考，和平交流
文章
215
标签
3
分类
3
Follow Me
目录
1.
cdq分治
最新文章
贪心
2024-12-22
Z函数与扩展KMP算法详解 - 以CF126B为例
2024-12-21
Codeforces Round 895 (Div. 3)
2024-12-16
可持久化字典树（Trie）
2024-12-16
网格图上问题
2024-12-15
搜索
数据加载中
