左神课堂

左神课堂开课啦！

我一直在想我到底是该刷题还是该学新知识点,但是我感觉我学的知识点都太浮躁了,根本就没有真正学会,所以我决定从头再来,在此,我决定,如果我会将每一个知识点都学完,如果我能在10月31号之前学完,我就奖励自己一个 影石Ace Pro 2.

1. 针对于gcd,最大公因数与容斥相关的一个性质,就是如果

裴蜀定理和扩展欧几里得算法

裴蜀定理

• a,b不全为0

重要理解:

1. a,b的最大公约数 = ax 和by,随意给定整数x,y,能得到 |ax - by| 的最小差值

2. ax + by = c有解,c一定是 gcd(a, b) 的整数倍[a,b不全为0]

3. 可以扩展到多项

扩展欧几里得算法

ax + by = gcd(a, b)

求解 一组(x, y),并且得到 gcd(a, b)

int d, x, y, lx, ly;

int gcd(int a, int b){
	if(!b){
		x = 1, y = 0, d = a;
		return;
	}else{
		gcd(b, a % b);
		lx = x, ly = y;
		x = ly;
		y = lx - ly * (a / b) * b;
	}
}

扩展欧几里得 – 二元一次不定方程

卡特兰数

感觉像递归分治.

[1,1,2,5,14,42,132]
[0,1,2,3, 4, 5, 6]

卡特兰数字的基本公式

应用场景

出进栈模型

1. 进出栈模型(括号匹配问题)

2. 一个圆上有n个点,连接 n-1 条线段,不相交(将奇数点作为’(‘,偶数点作为’)')

路径计数模型

主要思想: 映射关系(将集合进行映射来得到集合大小)

划分左右相乘模型

dp[n] =

前缀树