zcmimi's blog
avatar
zcmimi
2020-02-29

01背包

每个物品只能使用一次

普通多重背包

将可以用多次的物品拆为多个单次使用的物品

转化为01背包

二进制优化多重背包

但每个物品可以用的次数特别大的时候,如果还是直接拆很有可能会tle

[LG 1776 宝物筛选](https://www.luogu.com.c

avatar
zcmimi
2020-02-27

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

前置知识:

  1. FFT

  2. 原根

原根的性质

p是质数,g为模p的原根,n|(p-1),$g_n=g^{(

avatar
zcmimi
2020-02-25

FFT

fst fst tle

DFT: 离散傅里叶变换

IDFT: 离散傅里叶逆变换

FFT: 快速傅里叶变换

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

FWT: 快速沃尔什变换,利用类似FFT的东西解决一类卷积问题

MTT: 毛爷爷的FFT,非常nb/任意模数

FMT: 快速莫比乌斯变化

(摘自https://www.cnblogs.com/zwfymqz/p/8244902.html)

为什么要用到FFT呢?

以高精度乘法举个例子:

你现在要计算a\times b,a,b>10^{1000000}

len_a=n,len_b=m

如果用普通的高精度乘法\mathcal{O(nm)},直接tle

但是FFT可以做到\mathcal{O((n+m) \log (n+m))}

原理: 先把多项式转化为用点值表示\mathcal{O(n \log n)}

然后再用点值相乘来计算\mathcal{O(n)}

然后再通过点值还原多项式

avatar
zcmimi
2020-02-19

求解关于x的方程:

y^x \equiv z \pmod p

bsgs

\gcd(y,p)=1

解法:

x=am-b

那么y^{am} \equiv z\cdot a^b \pmod p

右边:

枚举b的取值[0,m-1],计算右边的

avatar
zcmimi
2020-02-01

Dynamic Rankings为例:

如果不带修改,那就是普通的主席树

待修改: 树状数组套动态开点权值线段树

对于修改a_p,

受影响的有[p,n]

但是我们不需要从p修改到n

可以

avatar
zcmimi
2020-01-30

换根树链剖分

loj #139.树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成$\frac{y{j1}-y{j2}}{x{j1}-x

avatar
zcmimi
2020-01-10

四边形不等式

定义

对于任意a_1\le a_2<b_1\le b_2,满足m[a_1,b_1]+m[a_2,b_2]\le m[a_1,b_2]+m[a_2,b_1]

那么m[i,j]满足四边形不等式

要证明m[i,j]满足四边形不等式可以用打表或数

avatar
zcmimi
2020-01-02

形态: 在一棵树上加多一条边

实现:

找出环后一次处理环上每个点的子树,然后再处理环

[IOI 2008]Island(求基环树直径)

IOI 2008 Island

先找出环,把环当根节点,找出每棵

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点$

6/73
Search
search