menu zcmimi's blog

arrow_back 算法

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

zcmimi
2020-04-16 22:39

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P383

zcmimi
2020-03-25 17:13

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线

zcmimi
2020-03-20 20:36

该好好复习(总结)一下莫比乌斯函数了呢\mathcal{>_\omega<}

定义

$$ \mu (i)= \begin{cases} 1,i=1 \ (-1)^k,i=p_1\tim

zcmimi
2020-03-12 20:40

扩展中国剩余定理

给定方程组:

$$ \begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \ x\equiv a_2\ ({\rm mod}\ m_2)

zcmimi
2020-03-07 15:50

Lucas定理

$$Cn^m\pmod p\equiv C{n\mod p}^{m\mod p} \cdot C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfl

zcmimi
2020-03-02

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

比如要合并集合A,B,设|A|<|B|

这时候将 向B中插入A 的效率要比 向A插入B

这就是启

zcmimi
2020-03-01

NTT基本上跟FFT一样,就是把单位根换成了原根(原根和单位根一样具有FFT需要的特殊性质)

前置知识:

  1. FFT(这里就不讲了)

  2. 原根

原根

阶:

zcmimi
2020-02-27

FFT

fst fst tle

DFT: 离散傅里叶变换

IDFT: 离散傅里叶逆变换

FFT: 快速傅里叶变换

FNTT/NTT: 快速傅里叶变换的优化

zcmimi
2020-02-25

求解关于x的方程:

y^x \equiv z \pmod p

BSGS

\gcd(y,p)=1

解法:

x=am-b

那么$y^{am} \equiv

zcmimi
2020-02-19
1 / 3
Search
search