听说明天有唐氏模拟赛，据说有\(tarjan\)
推歌：普通Disco/洛天依,言和 by ilem
呃呃呃我打算进行一个主席树和多项式的双开，同时写主席树和多项式
因为我主席树有点遇到了瓶颈，先学学数学看看，到时候一起写
\(wkh2008\)：开辟第二战场
多项式基础
-
多项式是什么
(初一知识点)
形如下面的表达式\(P(x)\)
\[\sum_{i=0}^{n}a_ix^i=a_0+a_1x+a_2x^2+\cdots+a_nx^n \]其中 \(a_i\) 表示多项式的系数
最高次项的指数 \(n\) 叫做多项式的度/次数
-
多项式乘法
(初一知识点)
定义两个多项式\(f(x)\)和\(g(x)\)其卷积的结果为
其卷积的结果为
\[h(x)=g(x)f(x)=\sum_{i=0}^{n}\sum_{j=0}^{m}g_if_jx^{i+j} \]还有另一个形式
\[h(x)=\sum_{i=0}^{n+m}\sum_{j=0}^{i}g_jf_{i-j}x^i \]-
一点都不严谨的证明
众所周知
\[(a_2x^2+a_1x^1)*(b_2x^2+b_1x^1)= a_2b_2x^3+a_2b_1x^2+a_1b_2x^2+a_1b_1x^2 \]设\(f(x)=a_2x^2+a_1x^1,g(x)=b_2x^2+b_1x^1\)
其乘积
\[h(x)=a_2b_2x^3+a_2b_1x^2+a_1b_2x^2+a_1b_1x^2=\sum_{i=0}^{2}\sum_{j=0}^{2}g_if_jx^{i+j} \]依次类比就能得出$$h(x)=g(x)f(x)=\sum_{i=0}{n}\sum_{j=0}g_if_jx^{i+j}$$
显然我们可以通过公式来\(\text O(nm)\)求解
-
-
\(\text {Karatsuba}\) 乘法
处理多项式乘法的一种方式，复杂度\(\text O(n^{\log3})\)
对于多项式\(f(x)\)我们让\(n=\deg f+1\)
那么
\[f(x)=\sum_{i=0}^{n-1}a_ix^i \]让
\[f(x)=f_0(x)+x^{\frac n2}f_1(x),g(x)=g_0(x)+x^{\frac n2}g_1(x) \]其中
\[\deg\ f_0=\deg\ f_1=\deg\ g_0=\deg\ g_1=\frac n2 \]那么我们可以得到一个式子
\[(f* g)(x)=(f_0* g_0)(x)+x^{\frac n2}(f_0* g_1+f_1* g_0)(x)+x^n(f_1* g_1)(x) \]令\(m(x)=((f_0+f_1)*(g_0+g_1))(x)\)
则$$(f_0* g_1+f_1* g_0)(x)=m(x)-(f_0* g_0)(x)-(f_1* g_1)(x)$$
只需要计算\(m,(f_0*g_0)(x),(f_1 *g_1)(x)\)即可
-
多项式的表示
-
系数表示
\[f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n \]把 \(a\) 数组看做 \(n+1\) 维向量 \(\vec{a}=(a_0,a_1,\cdots,a_n)\)，其系数表示为 \(\vec{a}\)
-
点值表示
\[f(x)=(x_0,f(x_0)),(x_1,f(x_1)),\cdots,(x_n,f(x_n)) \]
-
\(\text{FFT}\)
还记得这个式子吗
\[h(x)=\sum_{i=0}^{n+m}\sum_{j=0}^{i}g_jf_{j-i}x^i \]我们需要快速的求出\(h\)的每一项系数，但是明显做不到，点值表示却可以 \(O(n)\) 快速卷积
后面的 \(\text{wait for}\) 补全
