§1-10 多元多项式一、多元多项式的一些基本概念1、形如n k n k k x x ax 2121的表达式，其中a ∈R, k 1,k 2,…,k n 是非负整数，叫R 上x 1,x 2…x n 的单项式，a 叫单项式的系数，当a ≠0时，k 1+k 2+…+k n 叫单项式的次数.特别R x x Ox O R x x ax a n k n k k n n ∈=∈= 21210201也可看成单项式2、有限个单项式用加号联结起来而得到的一个形式表达式.sn s s n n k n k k x k n k k k n k k x x x a x x x a x x x a 21222211121121212211+++其中),2,1,,2,1(,n j s i k R a ij i ==∈是非负整数，叫做R 上n 个文字n x x x ,,,21 的一个多项式，简称一个n 元多项式.N 元多项式用),,,(),,,,(21211n n x x x g x x x f 等来表示，组成多项式的单项式叫做这个多项式的项.3、R 上两个n 元多项式说是相等的，当且仅当它们有完全相同的项，或者只差一些系数为0的项.4、R 上一个n 元多项式的次数指的是出现在这个多项式里次数最大的单项式的次数.5、如果),,,(21n x x x f 各项都有同一次数k ，那么就称它是一个k 次齐次多项式.二、R 上n 元多项式的运算1、R 上的n 元多项式),,,(21n x x x f 与),,,(21n x x x g 相加就是合并它们的同类项.记作),,,(),,,(21211n n x x x g x x x f +或f+g.2、设f 与g 都是R 上的n 元多项式，把f 的每一项与g 的每一项相乘，然后把这些乘积相加所得到的n 元多项式叫作f 与g 的积，记作fg.3、n 元多项式关于加法和乘法的运算律(1)(f+g)+h=f+(g+h), (fg)h=f(gh).(2)f+g=g+f, fg=gf.(3)(f+g)h=fh+gh.4、n 元多项式关于加法和乘法的次数设f,g 是R 上两个不等于0的n 元多项式，则有).()()()),(),(max()(000000g f fg g f g f ∂+∂=∂∂∂≤+∂5、n 元多项式环把数环R 上一切n 个文字n x x x ,,,21 的多项式所成的集合连同如上定义的加法和乘法叫做R 上n 个文字n x x x ,,,21 的多项式环，简称R 上n 元多项式环，记作R[n x x x ,,,21 ].三、n 元多项式的排序法数环R 上n 元多项式的一般形式可以写成n n i n i i i i i x x x a 212121Ξ1、按次数排序.)()()(),(30321222133020211220011000 ++++++++++=y a xy a y x a x a y a xy a x a y a x a a y x f ++++=)(),,(001010100000z a y a x a a z y x f++++++)(1101010112002202022000xy a xz a yz a z a y a x a .但这种排序法不能完全确定各项的次序.2、字典排序法设f(n x x x ,,,21 )是数环R 上的一个非零多项式n k n k k x x ax 2121(a ≠0) （2）n l n l l x x bx 2121(b ≠0) （3）是f 的两个不同的项，若有一个i(1≤i ≤n)使k 1=l 1,…k i-1=l i-1，但k i >l i则称项（2）大于项（3）（或项（3）小于项（2）），把多项式f(n x x x ,,,21 )的项按这种大于关系排列的方法叫字典排列法，多项式f(n x x x ,,,21 )按字典排列法书写后的第一项叫做f(n x x x ,,,21 )的首项.Ex 按字典排序法排41321243221423432132),,,(x x x x x x x x x x x x f ++--=.解：23),,,(42324322133221414321---+=x x x x x x x x x x x x x f . Th 数环R 上两个n 元多项式f(n x x x ,,,21 )与g(n x x x ,,,21 )的乘积的首项等于这两个多项式首项的乘积，特别两个非零多项式的乘积也不等于零.四、n 元多项式函数及n 元多项式的零点Def: 给定了R 上一个n 元多项式f(n x x x ,,,21 )，n n R c c c ∈∀),,(21 ，规定),,,(),,(2121n n c c c f c c c →，这样定义的R n →R 的函数叫做由多项式f(n x x x ,,,21 )所确定的多项式函数. 如果),,,(,0),,(2121n n c c c c c c f 则=叫f(n x x x ,,,21 )的一个零点.Th 数环R 上的多项式f(n x x x ,,,21 )与g (n x x x ,,,21 )相等，当且仅当，这两个多项式议的多项式函数相等.。
多项式各种算法学习笔记1.FFT(快速傅⾥叶变换)1.前置技能复数:基本表⽰法及性质:\[i=\sqrt{-1} \]\(i\)是虚数单位1.坐标(代数)形式：\[z=a+bi \]当b为0是z为实数，当a为0时为纯虚数注:复数包括实数和虚数，虚数下有纯虚数虚数z对应了复平⾯上的⼀点(a,b)运算法则：设复数\(z_1,z_2,z_1=a+bi,z_2=c+di\)加法:\(z_1+z_2=(a+c)+(b+d)i\)减法:\(z_1-z_2=(a-c)+(b-d)i\)乘法:\(z_1*z_2=(ac-bd)+(bc+ad)i\)除法:\(\dfrac{z_1}{z_2}=\dfrac{(ac+bd)+(bc-ad)i}{(c^2+d^2)}\)2.三⾓形式\[z=r(cos \theta+isin\theta) \]\(\theta\)是复数\(z\)的幅⾓,\(r\)是该复数的模长这种形式下的乘法和除法运算更⽅便，通过和⾓公式，对于复数\(z_1=r_1(cos\theta_1+isin\theta_1),z_2=r_2(cos\theta_2+isin\theta_2)\)那么：\[z_1z_2=r_1r_2(cos(\theta_1+\theta_2)+isin(\theta_1+\theta_2))\\ \dfrac{z_1}{z_2}=\dfrac{r_1}{r_2}(cos(\theta_1-\theta_2)+isin(\theta_1-\theta_2))\\ \]⼏何意义:相当于把该复数拉长/缩短到另⼀个复数模长倍/分之⼀ ,然后顺时针/逆时针旋转另⼀个复数的幅⾓⼤⼩的⾓度于是有了如下⾮常有⽤的公式:\[z^n=(r(cos\theta+isin\theta))^n=r^n(cos\ n\theta+isin\ n\theta) \]3.指数形式\[z=re^{i\theta} \]于是我们知道了:\(e^{i\theta}=cos\theta+isin\theta\)可以发现:$$e^{i\pi}=-1$$(优美)这个算乘除法就更好算了:有:\[z_1z_2=r_1r_2e^{i(\theta_1+\theta_2)}\\ \dfrac{z_1}{z_2}=\dfrac{r_1}{r_2}e^{i(\theta)}\\ \]上⾯的那个公式就可写成这样：\[z^n=r^ne^{i(n\theta)} \]4.单位复数根学FFT最重要的就这个了吧设有如下⽅程:\[z^n=1 \]这⽅程的复数根\(z\)为\(n\)次单位根,通常记为\(w\)这样的根\(w\)有n个，也就是说\(n\)次单位根有\(n\)个,记为\(w_k (k=0,1,2,\dots n-1)\)其中:\[w_k=cos\frac{2k\pi}{n}+isin\frac{2k\pi}{n}=e^{\frac{2\pi ki}{n}} \]不难发现其实\(n\)次单位复数根就是把复平⾯上的单位圆 \(n\) 等分后的那些\(n\)等分点⼀些次数单位的单位根举例:1次单位根: \(1\)2次单位根: \(1,-1\)3次单位根: \(1,\frac{-1+\sqrt{3}i}{2},\frac{-1-\sqrt{3}i}{2}\)\(\dots\)其实就是个解⼆元n次⽅程可以发现1是任意次的单位复数根，-1是任意偶数次单位复数根某些引理:1.消去引理\[w_{dn}^{dk}=w_n^k \]把复数的指数形式带进去就可以了说⼈话就是不同次数的单位根可以互相转化2.折半引理假设\(n\)是⼤于0的偶数:\[(w_n^{k+\frac{n}{2}})^2=w_n^{2k+n}=w_n^{2k}*w_n^n=(w_n^{k})^2 \]说⼈话就是n次单位复数根的前后两半平⽅后是对应相等的3.求和引理对于⼤于1的整数n和⼩于等于n的整数k有:\[\sum_{i=0}^{n-1}(w_n^k)^i=0 \]这就是个等⽐数列求和2.步⼊正题常规的⼀个最⾼次数为n-1的多项式的表⽰形式是系数表⽰法,如:\[A(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots+a_{n-1}x^{n-1} \]⼀共有n项按照朴素的多项式乘法(卷积),就是每⼀项两两相乘，复杂度为\(O(n^2)\)如果我们把多项式看成⼀个函数，我们取图像上的n个点来表⽰这个函数也即该多项式，这样的表⽰法叫做点值表⽰法对于两个n-1次多项式,由于我们最后卷积出来的多项式是2n-2次的,如果我们知道了卷积后的多项式函数图像上的⾄少2n-1个点，那么我们就可以确定这个多项式了所以有如下想法：现在原来的两个多项式上选取好x值相同的点(个数为原来两多项式次数的和加1)，⽤\(O(n)\)的时间将选的点的y值相乘，得到的值⽤某种⽅法(待定系数法)转化为多项式系数的形式如果选取的x都是n次单位复数根的k次⽅，那么以上两个过程就是\(DFT\)和\(IDFT\)了1.\(DFT\)离散傅⾥叶变换：对于\(k\in [0,n-1],\)和n-1次多项式\(A(x),\)定义:\[y_k=A(w_n^k)=\sum_{i=0}^{n-1}a_i(w_n^k)^i \]这个叫做离散傅⾥叶变换，记做\(y=DFT_n(a)\)朴素求\(DFT\),是\(O(n^2)\)的2.\(IDFT\)逆离散傅⾥叶变换:就是\(DFT\)的逆运算，⽤于求出多项式的系数a，记为\(DFT^{-1}\)本⼈太弱不会证，丢个式⼦:\[a_k=\dfrac{1}{n}\sum_{i=0}^{n-1}y_i(w_n^{-k})^i \]由于写的时候系数表达式和点值表达式是共⽤的数组，所以写起来和\(DFT\)没什么差别3.\(FFT\)快速傅⾥叶变换:是⼀种快速求出\(DFT\)和\(DFT^{-1}\)的算法，利⽤了单位复数根的优良性质我们先列出朴素求\(DFT\)的步骤,为了⽅便这⾥先不妨假设多项式次数为2的幂:1.求出n次单位复数根的幂:\(w_n^0,w_n^1,w_n^2.....w_n^{n-1}\)2.代⼊多项式\(A(x)\),求得以下式⼦:\[A(w_n^0)=a_0+a_1w_n^0+a_2(w_n^0)^2+a_3(w_n^0)^3+\dots a_{n-1}(w_n^0)^{n-1}\\A(w_n^1)=a_0+a_1w_n^1+a_2(w_n^1)^2+a_3(w_n^1)^3+\dots a_{n-1}(w_n^1)^{n-1}\\ A(w_n^2)=a_0+a_1w_n^2+a_2(w_n^2)^2+a_3(w_n^2)^3+\dots a_{n-1}(w_n^2)^{n-1}\\ A(w_n^3)=a_0+a_1w_n^3+a_2(w_n^3)^2+a_3(w_n^3)^3+\dots a_{n-1}(w_n^3)^{n-1}\\\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\\ A(w_n^{n-1})=a_0+a_1w_n^{n-1}+a_2(w_n^{n-1})^2+a_3(w_n^{n-1})^3+\dots a_{n-1}(w_n^{n-1})^{n-1}\\ \]根据折半引理,我们可以发现:对于⼀个\(A(w_n^k)\),\((k<\frac{n}{2})\)它的每⼀个偶数次⽅项与\(A(w_n^{k+\frac{n}{2}})\)是对应相同的以n=4的情况来考虑:就是要求:\[A(w_4^0)=a_0+a_1w_4^0+a_2(w_4^0)^2+a_3(w_4^0)^3\\ A(w_4^1)=a_0+a_1w_4^1+a_2(w_4^1)^2+a_3(w_4^1)^3\\A(w_4^2)=a_0+a_1w_4^2+a_2(w_4^2)^2+a_3(w_4^2)^3\\ A(w_4^3)=a_0+a_1w_4^3+a_2(w_4^3)^2+a_3(w_4^3)^3\\ \]把每⼀个多项式的偶数次数项的系数提出来组成的多项式记为\(A^{[0]}(x)\),奇数项记为\(A^{[1]}(x)\)那么有:\[A^{[0]}((w_4^0)^2)=A^{[0]}((w_4^2)^2)\\ a_0=a_0\\ a_1(w_4^0)^2=a_1(w_4^2)^2\\ \]\[A^{[0]}((w_4^1)^2)=A^{[0]}((w_4^3)^2)\\ a_0=a_0\\ a_1(w_4^1)^2=a_1(w_4^3)^2\\ \dots\\ \]奇数项就没有这么优美的性质,但是我们可以提出来⼀个x使得它变成偶数项所以我们现在考虑把⼀个多项式奇偶分组:显然会有如下结论:\[A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2) \]就是\[A(w_4^0)=A^{[0]}((w_4^0)^2)+w_4^0A^{[1]}((w_4^0)^2)\\ A(w_4^1)=A^{[0]}((w_4^1)^2)+w_4^1A^{[1]}((w_4^1)^2)\\ A(w_4^2)=A^{[0]}((w_4^2)^2)+w_4^2A^{[1]}((w_4^2)^2)\\ A(w_4^3)=A^{[0]}((w_4^3)^2)+w_4^3A^{[1]}((w_4^3)^2)\\ \]折半引理化简⼀下:\[A(w_4^0)=A^{[0]}(w_2^0)+w_4^0A^{[1]}(w_2^0)\\ A(w_4^1)=A^{[0]}(w_2^1)+w_4^1A^{[1]}(w_2^1)\\ A(w_4^2)=A^{[0]}(w_2^0)+w_4^2A^{[1]}(w_2^0)\\ A(w_4^3)=A^{[0]}(w_2^1)+w_4^3A^{[1]}(w_2^1)\\ \]那么我们知道如果把上⾯的分成两半,根据折半引理:前后两半对应的只有后⾯要乘上的单位复数根不⼀样,所以其实我们已经把问题的规模缩⼩了⼀半了,因为我们只需求解如下东西:\[A^{[0]}(w_2^0)\\ A^{[1]}(w_2^0)\\ A^{[0]}(w_2^1)\\ A^{[1]}(w_2^1)\\ \]\(P.S.\)其实我们还可以发现:\[因为ω_n^\frac{n}{2}=e^{k\pi i}=coskπ+isinkπ=−1\\ 所以A(ω^{k+\frac{n}{2}}_n)=A^{[0]}(ω^k_\frac{n}{2})−ω^k_nA^{[1]}(ω^k_\frac{n}{2})\\ \]所以说其实只是后⾯的系数的符号不⼀样再来观察⼀下现在要求的东西,可以发现如果把整个⼦问题也进⾏奇偶分组的话,每⼀组其实要求的是长度为原来⼀半的\(DFT\),如果采⽤递归进⾏处理,那么递归分组⼀次之后要求的⼦问题是:\[A^{[0]}(w_2^0)=a_0+a_2w_2^0\\ A^{[0]}(w_2^1)=a_0+a_2w_2^1\\ ---------------\\ A^{[1]}(w_2^0)=a_1+a_3w_2^0\\ A^{[1]}(w_2^1)=a_1+a_3w_2^1\\ \]于是我们只要计算这4个⼦问题原\(DFT\)的两边就都可以直接算出来了并且对于该⼦问题,我们也只需求解\(A^{[0]}(w_2^0)和A^{[1]}(w_2^0)\),另⼀半也是和上⾯的⼀样由这⼀半推出,因为这是⼀个长度为原来⼀半的\(DFT\)我们先看看递归版应该怎么实现:1.不停将要求的\(DFT\)进⾏奇偶分组并递归下去2.如果只有⼀个元素,显然这时\(x=w_1^0=1\),直接返回当前的系数就可以了3.合并答案:把每层要求的东西写出来:\[A(w_4^0)\;\;\;\;A(w_4^1)\;\;\;\;A(w_4^2)\;\;\;\;A(w_4^3)\\ A^{[0]}(w_2^0)\;\;A^{[0]}(w_2^1)\;\;A^{[1]}(w_2^0)\;\;A^{[1]}(w_2^1)\\a_0\;\;\;\;\;\;\;\;\;\;\;a_2\;\;\;\;\;\;\;\;\;\;\;\;\;a_1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_3\\ \]根据上⾯的公式就很容易知道每个元素是由下⼀层的哪⼀个得来的了,这很像个蝴蝶,于是被成为蝴蝶操作还没有理解的话可以看看8的情况,建议⾃⼰⼿画⼀下,标出贡献来源,这样就很容易理解了\[A(w_8^0)\;\;\;\;\;\;A(w_8^1)\;\;\;\;\;\;A(w_8^2)\;\;\;\;\;\;A(w_8^3)\;\;\;\;\;\;A(w_8^4)\;\;\;\;\;\;A(w_8^5)\;\;\;\;\;\;A(w_8^6)\;\;\;\;\;\;A(w_8^7) \]\[A^{[0]}(w_4^0)\;\;\;\;\;\;A^{[0]}(w_4^1)\;\;\;\;\;\;A^{[0]}(w_4^2)\;\;\;\;\;\;A^{[0]}(w_4^3)\;\;\;\;\;\;A^{[1]}(w_4^0)\;\;\;\;\;\;A^{[1]}(w_4^1)\;\;\;\;\;\;A^{[1]}(w_4^2)\;\;\;\;\;\;A^{[1]}(w_4^3) \]\[A^{[0]^{[0]}}(w_2^0)\;\;\;\;A^{[0]^{[0]}}(w_2^1)\;\;\;\;A^{[0]^{[1]}}(w_2^0)\;\;\;\;A^{[0]^{[1]}}(w_2^1)\;\;\;\;A^{[1]^{[0]}}(w_2^0)\;\;\;\;A^{[1]^{[0]}}(w_2^1)\;\;\;\;A^{[1]^{[1]}}(w_2^0)\;\;\;\;A^{[1]^{[1]}}(w_2^1) \]\[a_0\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_4\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_2\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_6\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_1\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_5\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_3\;\;\;\;\;\;\;\;\;\;\;\;\;\;a_7 \]从下往上蝴蝶的跨度不断增⼤,倒数第2层就是相邻的两个元素宽度半径为1,然后往上不断倍增,每⼀次只是改变两个位置对应的数,所以其实也可以写成⾮递归的但是我们需要最后分组后的最下⾯⼀层其实每个数最后在的位置是他的⼆进制反序数,所以是⼀个Rader排序(⼆进制反转),这个并不是⾮常重要,记⼀下就差不多了贴个⾮递归的板⼦:#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<cstdlib>using namespace std;inline int read(){int x=0;char ch=getchar();int t=1;for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);return x*t;}typedef long long ll;typedef double db;const db PI=acos(-1);struct Complex{//⼿写复数db x,y;Complex(db x1=0.0,db y1=0.0){x=x1,y=y1;}inline Complex operator +(const Complex &b)const{return Complex(x+b.x,y+b.y);}inline Complex operator -(const Complex &b)const{return Complex(x-b.x,y-b.y);}inline Complex operator *(const Complex &b)const{return Complex(x*b.x-y*b.y,x*b.y+y*b.x);}inline void init(){x=read();}inline void out(){printf("%lf %lf\n",x,y);}};typedef Complex C;const int N=4e6+10;int r[N],l;int n,m;C a[N],b[N];inline void FFT(C *P,int f){for(register int i=0;i<n;++i) if(i<r[i]) swap(P[i],P[r[i]]);for(register int i=1;i<n;i<<=1){//枚举每⼀层蝴蝶操作的跨度C W(cos(PI/i),f*sin(PI/i));//同层所需要的单位根是相同的(是蝴蝶操作直径次单位根)for(register int p=i<<1,j=0;j<n;j+=p){//两倍当前蝴蝶操作半径为⼀组(这⾥是多项式系数奇偶分组后的组数)C w(1,0);for(register int k=0;k<i;++k,w=w*W){//每组内有蝴蝶操作直径个⼦DFT,但是蝴蝶操作每次处理两个,只要枚举到半径的长度C X=P[j+k],Y=w*P[j+k+i];P[j+k]=X+Y,P[j+k+i]=X-Y;}}}}int main(){n=read();m=read();for(register int i=0;i<=n;++i) a[i].init();for(register int i=0;i<=m;++i) b[i].init();m+=n;l=0;for(n=1;n<=m;n<<=1) ++l;//补成2的幂for(register int i=1;i<n;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);//RaderFFT(a,1); FFT(b,1);for(register int i=0;i<n;++i) a[i]=a[i]*b[i];FFT(a,-1);for(register int i=0;i<=m;++i) printf("%d ",(int)(a[i].x/n+0.5));//IDFT最后除nreturn 0;}注意事项:1.由于FFT有⼤量实数运算,不仅常数⼤,精度也会有很⼤问题,转化为整数时要四舍五⼊。
多项式恒等定理多项式恒等定理是代数学中的重要定理之一，它描述了多项式的恒等关系。
首先，什么是多项式？多项式是一个基本数学概念，它是由系数和幂指数的和组成的表达式。
一般来说，一个n次多项式可以写成以下形式：P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ其中，a₀, a₁, a₂, ... , aₙ为任意实数或复数，x为未知数，n为非负整数。
在这个表达式中，a₀, a₁, a₂, ... , aₙ为多项式的系数，x为多项式的变量，n为多项式的次数。
而多项式恒等定理正是研究多项式之间恒等关系的定理。
多项式恒等定理可以分为两个方向：多项式相等和多项式不等式。
首先，我们来看多项式相等的情况。
在多项式相等的情况下，两个不同的多项式在某些条件下可以证明它们是相等的。
常见的多项式相等定理有：1. 多项式的表示唯一性定理：对于给定的一元多项式P(x)，它的表示形式是唯一的，即不存在两个不同的多项式Q(x)和R(x)，使得P(x) = Q(x) = R(x)成立。
2. 多项式根与系数关系定理：对于给定的一个n次多项式P(x)，它的根与系数之间存在一种确定的关系。
例如，对于二次多项式ax² + bx + c，它的根x₁和x₂满足x₁ + x₂ = -b/a，x₁x₂ =c/a。
这个定理可以通过将多项式P(x)进行因式分解来证明。
接下来，我们来看多项式不等式的情况。
在多项式不等式的情况下，多项式之间的关系是不等关系，即存在一个条件，使得某个多项式大于或小于另一个多项式。
常见的多项式不等定理有：1. 多项式的增减性定理：对于给定的一个n次多项式P(x)，当x在一个区间内递增或递减时，多项式的值也随之递增或递减。
这个定理可以通过多项式的导数和导函数的性质来证明。
2. 多项式不等性定理：对于给定的两个不同的多项式P(x)和Q(x)，可以通过比较它们的系数和次数的关系来确定它们的不等关系。
