多项式与生成函数

多项式


表示

系数表示法:$F(x)=\sum\limits_{i=0}^{n}a_ix^i$

点值表示法:$(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$

对于多项式$A(x)$,称其最高项的次数为这个多项式的,记作$degA$


运算

多项式加减:采用系数表示法,进行向量加减

多项式乘法:采用点值表示法,将点的坐标相乘


快速傅里叶变换(FFT)

基础知识部分待填坑

DTF:系数表示法->点值表示法
逆DFT:点值表示法->系数表示法
利用单位复数根的性质,可以在$O(n \log n)$的时间复杂度内完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef complex<double> C;//复数库

void pre()
{
m=n<<1;
for(n=1;n<=m;n<<=1) L++;
for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));//求逆序表:末位为0,直接为其前一半逆序表的值右移一位,末位为1,在最高位添加1
}

void FFT(C *a,int f){
for(int i=0;i<n;i++) if(R[i]>i) swap(a[i],a[R[i]]);//利用逆序表,快速求逆序
for(int i=1;i<n;i<<=1){
C wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<n;j+=i<<1){
C w(1,0);for(int k=0;k<i;k++,w*=wn){
C x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;a[j+k+i]=x-y;
}
}
}
if(f==-1) for(int i=0;i<n;i++) a[i]/=n;
}
笔记


快速数论变换(NTT)

FFT的缺点:常数大,炸精度,无法在模意义下求解

新的算法

数论意义下

一般模数$P=a \cdot 2^m +1,a$是一个较小的数

用原根代替单位复数根

笔记


快速沃尔什变换(FWT)

大坑待填

笔记


多项式求逆

对于多项式$A(x),B(x)$,存在唯一的$Q(x),R(x)$
满足$A(x)=Q(x)B(x)+R(x)$,其中$degR<degB$
称$Q(x)$为$B(x)$除$A(x)$的,$R(x)$为$B(x)$除$A(x)$的余数
记作$A(x) \equiv R(x) \pmod {B(x)}$

对于多项式$A(x)$,若存在$B(x)$满足$degB≤degA$,
并且$A(x)B(x) \equiv 1 \pmod {x^n}$,那么称$B(x)$为$A(x)$在$mod$ $x^n$意义下的逆元,记作$A^{-1}(x)$

采用倍增思想,设$B(x)$为$\bmod x^{\lceil \frac{n}{2} \rceil}$意义下$A(x)$的逆元

经过推导,最后可以得到

递归$FFT$就可以搞了,同时易知多项式有逆元的充分必要条件为常数项有逆元

$O(n \log n)$,常数约为$FFT$的$6$倍

推导


多项式除法

大坑待填


多项式取模

大坑待填


牛顿迭代法

给出$G(x)$,求$F(x)$,满足


多项式开方

求$B^2(x) \equiv A(x) \pmod {x^n}$

类似多项式求逆,设$B_0(x)$为$\bmod x^{\lceil \frac{n}{2} \rceil}$意义下$A(x)$的平方根

整理后得到

$O(n \log n)$


多项式In

求导……


多项式exp

取对数后使用牛顿迭代法


多项式k次幂

……


多项式复合

……


多项式多点求值与插值

多点求值:给出多项式$A(x)$和$n$个点$x_0, x_1, \cdots, x_{n-1}$,要求求出$A(x_0)$, $A(x_1)$, $\cdots$, $A(x_{n-1})$

插值:给出n+1个点$(x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)$,求出一个$n$次多项式,使得这些点都在这个多项式上

大力搞搞……


参考资料


生成函数


考虑一类组合对象组成的集合 $A$,其中,
每个元素$a ∈ A$都被定义了“大小”$|a|$,它是一个非负整数
对于给定的$n$,大小为$n$的元素的数量是有限的,记作$A_n$

普通型生成函数

定义序列$a_n$的普通型生成函数 (Ordinary Generating Function, OGF),为

基本运算

有两类组合对象$A$和$B$

  • 定义$ C $为$A$和$B$的并集

    $C(x) = A(x) + B(x)$

  • 定义$ D $为$ A $和$ B $的笛卡尔积

    $D $的每个元素 $d $都是$ A $的某元素$ a $与$ B $的某元素$ b $拼成的二元
    组$ (a, b)$,其大小$ |d| $定义为$ |a| + |b|$

    $D(x) = A(x)B(x)$

指数型生成函数

定义序列$a_n$的指数型生成函数 (Exponential Generating Function, EGF) ,为

伯努利数

分享到: