多项式 ​

基础知识：
	基本结论1：n次多项式的系数可以由n+1个两两不同的点确定
	基本结论2：范德蒙德方阵*系数矩阵=点值矩阵
		推广：
			范德蒙德方阵有逆当且仅当没有两行相同
			就是没有两个相同的点值，这和结论1符合
			那么，有了点值，就能推出系数
			有了系数，就能推出点值
拉格朗日插值
	作用：点值得系数
	具体处理：
		假设已有n+1个点值是(xi,yi)，我们要使得f(xi)=yi
		类似CRT，我们可以对于i，构造：
			yi*(x-x1)*(x-x2)*...*(x-x(i-1))*(x-x(i+1))*...*(x-xn)/(xi-x1)*(xi-x2)*...
		这样，就构造出了对应的多项式
	应用：
		可以O(n^2)求出多项式的点值
		在xi连续时，有线性做法
快速傅里叶（逆）变换
	作用：快速实现系数和点值的互相转化
	注意：
		FFT的本质是对于范德蒙德矩阵乘上系数矩阵的求解
		DFT的本质是对于范德蒙德逆矩阵乘上点值矩阵的求解
		所以两者的实现过程非常相似
	FFT应用的性质：
		性质1：
			f(x)=f1(x^2)+xf2(x^2)
			f(-x)=f1(x^2)-xf2(x^2)
			其中，f1是f偶项,f2是f奇项
			利用这个，我们可以递归快速得到点值
		性质2：
			根据我们递归的函数划分方法，容易发现最终系数的位置有：
			蝴蝶变换：将一个数在[0,2^l-1]的二进制反转
			这样，我们可以实现非递归
		性质3：
			因为DFT的需要，我们代入单位根作为点
			w[2l][i+l]=-w[2l][i]
			w[2l][i]^2=w[l][i]
			f(w[2l][i])=f1(w[l][i])+w[2l][i]*f2(w[l][i])
			f[w[2l][i+l])=f1(w[l][i])-w[2l][i]*f2(w[l][i])
	DFT的推导：
		核心：(x-w0)*(x-w1)*...*(x-w(n-1))=x^n-1
		利用拉格朗日插值，结合这个进行一定的多项式推导，可以得到范德蒙德的左逆矩阵
		即原矩阵的每一位取倒数并乘1/n
快速数论变换
	原根和单位根是同构的，所以直接代替即可
	常数优化：16次循环取模

快速沃尔什变换
	与卷积（或卷积同理）：
		前置知识：高维前缀和及其逆变换
		具体处理：
			对于A*B=C的与卷积
			我们现对A,B求高维前缀和，将其对应下标乘起来
			那么这就是C的高维前缀和，然后做逆变换即可还原C
	异或卷积：
		首先应该明确我们要构造fwt[A][i]*fwt[B][i]=fwt[C][i]
		然后我们套用范德蒙德矩阵的形式，考虑还是将fwt[i]表示成各项系数的和
		那么经过推导，可以得到c(i,j)*c(i,k)=c(i,j^k)
		然后因为是位运算，而且我们的目的是构造解，所以考虑特解-按位分解
		那么利用每一位的限制，可以推导得到c(0/1,0/1)
		或及与的不再赘述，异或的矩阵是{{1,1},{1,-1}}，逆是全乘1/2
		那么，我们可以写出范德蒙德矩阵
		然后，你会发现FWT和FFT的惊人的相似性，只能说比较凑巧
		事实上，其本质是每次新考虑一个位，然后分类处理
		求逆可以最后乘上1/2^n

重要结论：
    在fft和fwt中，本质上我们将多项式转化成了 点值表示法
    那么：
    	多项式加法可以转化成点值的加法
    	多项式卷积可以转化成点值的乘法
	所以，多项式的常见两个操作都是复杂度线性的（除去变换复杂度）

{max,+}卷积：
	加法对应了max，乘法对应了加法
	注意，这仍然是有结合律和分配律的
	常见是凸函数的卷积
	具体实现见闵可夫斯基和

基础知识：
	基本结论1：n次多项式的系数可以由n+1个两两不同的点确定
	基本结论2：范德蒙德方阵*系数矩阵=点值矩阵
		推广：
			范德蒙德方阵有逆当且仅当没有两行相同
			就是没有两个相同的点值，这和结论1符合
			那么，有了点值，就能推出系数
			有了系数，就能推出点值
拉格朗日插值
	作用：点值得系数
	具体处理：
		假设已有n+1个点值是(xi,yi)，我们要使得f(xi)=yi
		类似CRT，我们可以对于i，构造：
			yi*(x-x1)*(x-x2)*...*(x-x(i-1))*(x-x(i+1))*...*(x-xn)/(xi-x1)*(xi-x2)*...
		这样，就构造出了对应的多项式
	应用：
		可以O(n^2)求出多项式的点值
		在xi连续时，有线性做法
快速傅里叶（逆）变换
	作用：快速实现系数和点值的互相转化
	注意：
		FFT的本质是对于范德蒙德矩阵乘上系数矩阵的求解
		DFT的本质是对于范德蒙德逆矩阵乘上点值矩阵的求解
		所以两者的实现过程非常相似
	FFT应用的性质：
		性质1：
			f(x)=f1(x^2)+xf2(x^2)
			f(-x)=f1(x^2)-xf2(x^2)
			其中，f1是f偶项,f2是f奇项
			利用这个，我们可以递归快速得到点值
		性质2：
			根据我们递归的函数划分方法，容易发现最终系数的位置有：
			蝴蝶变换：将一个数在[0,2^l-1]的二进制反转
			这样，我们可以实现非递归
		性质3：
			因为DFT的需要，我们代入单位根作为点
			w[2l][i+l]=-w[2l][i]
			w[2l][i]^2=w[l][i]
			f(w[2l][i])=f1(w[l][i])+w[2l][i]*f2(w[l][i])
			f[w[2l][i+l])=f1(w[l][i])-w[2l][i]*f2(w[l][i])
	DFT的推导：
		核心：(x-w0)*(x-w1)*...*(x-w(n-1))=x^n-1
		利用拉格朗日插值，结合这个进行一定的多项式推导，可以得到范德蒙德的左逆矩阵
		即原矩阵的每一位取倒数并乘1/n
快速数论变换
	原根和单位根是同构的，所以直接代替即可
	常数优化：16次循环取模

快速沃尔什变换
	与卷积（或卷积同理）：
		前置知识：高维前缀和及其逆变换
		具体处理：
			对于A*B=C的与卷积
			我们现对A,B求高维前缀和，将其对应下标乘起来
			那么这就是C的高维前缀和，然后做逆变换即可还原C
	异或卷积：
		首先应该明确我们要构造fwt[A][i]*fwt[B][i]=fwt[C][i]
		然后我们套用范德蒙德矩阵的形式，考虑还是将fwt[i]表示成各项系数的和
		那么经过推导，可以得到c(i,j)*c(i,k)=c(i,j^k)
		然后因为是位运算，而且我们的目的是构造解，所以考虑特解-按位分解
		那么利用每一位的限制，可以推导得到c(0/1,0/1)
		或及与的不再赘述，异或的矩阵是{{1,1},{1,-1}}，逆是全乘1/2
		那么，我们可以写出范德蒙德矩阵
		然后，你会发现FWT和FFT的惊人的相似性，只能说比较凑巧
		事实上，其本质是每次新考虑一个位，然后分类处理
		求逆可以最后乘上1/2^n

重要结论：
    在fft和fwt中，本质上我们将多项式转化成了 点值表示法
    那么：
    	多项式加法可以转化成点值的加法
    	多项式卷积可以转化成点值的乘法
	所以，多项式的常见两个操作都是复杂度线性的（除去变换复杂度）

{max,+}卷积：
	加法对应了max，乘法对应了加法
	注意，这仍然是有结合律和分配律的
	常见是凸函数的卷积
	具体实现见闵可夫斯基和