平面几何、多项式、斯特林数听课随笔

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135166276

平面几何

知识点：

1. 平面凸包

2. 闵和，闵可夫斯基和 P4557

3. 旋转卡壳

4. 半平面交

5. 最小圆覆盖 P4586

• P9544
  $\{v_1,v_2,..,v_n\}$ 的凸组合，满足 $\alpha_1v_1+\alpha_2v_2+\dots\alpha_nv_n,\alpha_i\ge 0,\sum_i\alpha_i=1$

多项式

NTT： $F_p$ 下的FFT。（有些 $p$ 的 $F_p$ 有单位跟状物（原根的某个幂））

另一种卷积：分治。 $C=AB$ ， $A=A_o+A_1x^n,B=B_0+B_1x^n$ 。则 $C=(A_0+A_1x^n)(B_0+B_1x^n)=A_0B_0+(A_0B_1+A_1B_0)x^n+A_1B_1x^{2n}$ 。

观察到： $A_0B_1+A_1B_0=(A_0+A_1)(B_0+B_1)-A_0B_0-A_1B_1$ ，复杂度约为 $O(n^{1.585})$ 。

而此时 $x$ 为一个形式，所以不需要什么单位根的。更具体，这个方法只要求系数所属集合构成一个“环”（模4意义是环，整数是环）

因此可以做任意模数！常数很小！

多项式要会那些东西的平方做法（比如维护分段函数、点值做操作等等（对很小的多项式进行操作））

斯特林数

下讲幂多项式表示和普通幂的互化

$n$ 次多项式：可以表示 $a_nx^n+a_{n-1}^{n-1}+...$ ，也可以表示为 $n$ 下降幂