zcmimi's blog

categories/note/共63篇文章

avatar
zcmimi
2020-07-05 15:56:00

阶:

定义:

m>1\gcd(a,m)=1,那么使得a^r \equiv 1 \pmod m成立的最小的正整数r称为a对模m的阶,记为\delta_m(a),或ord_m a

定理:

  1. m>1gcd(a,m)=1,满足$a^n\
avatar
zcmimi
2020-07-01 13:58:00

定义

n个元素中取出m个的方案数,记为n\choose mC_n^m

{n\choose m}=\frac{n!}{m!(n-m)!}

帕斯卡法则

{n-1\choose m}+{n-1\choose m-1}={n\choose m}

avatar
zcmimi
2020-06-25

推荐:

定义

生成函数又称母函数

设序列aa_0,a_1,a_2,\dots

avatar
zcmimi
2020-06-22 21:09:00

https://www.51nod.com/Challenge/Problem.html#problemId=1822

定义

$$ \begin{cases} B0=1\~\ \displaystyle \sum\limits{i=0}^n {n+1\choose i}B_i=0,

avatar
zcmimi
2020-06-01 13:28:00
avatar
zcmimi
2020-05-18 21:43:00

数据结构

    • 单调栈
  • 队列

    • 单调队列
    • 优先队列
    • 双端队列
    • 二叉堆
    • 可并堆
      • 左偏树
      • 配对堆
      • 斐波那契堆
  • 并查集

    • 路径压缩
    • 按秩合并
    • 可持久化并查集
  • 线

avatar
zcmimi
2020-05-13 19:00:00

简介

后缀数组,又称SA

是OI中处理字符串的有力工具

实现

有两种实现的方法

  1. 倍增法
  2. DC3

这里主要讲倍增法

sa[i]表示所有后缀中的字典序排名为i的后缀的起始位置

rnk[i]表示起始位置为i的后缀(后缀i)在所有后缀中的排名

avatar
zcmimi
2020-04-16 22:39:00

核心思想: 把一个修改看成一个区间,每个询问是一个叶子,修改在线段树上打标记

avatar
zcmimi
2020-04-14 10:26:00

简介

k-D Tree(KDT,k-Dimension Tree)是一种可以高效处理k维空间信息的数据结构。

维基百科

在算法竞赛的题目中,一般k=2

构建

`

avatar
zcmimi
2020-03-29 16:58:00

link-cut tree是一个挺复杂的东西,本文主要用于复习巩固link-cut tree

推荐:

#

3/7
Search
search