一、理解

快速求两个多项式相乘。朴素做法就是暴力枚举两个多项式的每一项【】。FFT，先用点值法（后面解释）把多项式表示出来（DFT过程）【】，再计算点值相乘【】，然后再把点值法还原成系数法（后面解释）表示（IDFT过程）【】。

点值法：涉及线代，简单理解就是把多项式看为函数。中学知识告诉我们，n个未知数（这里的未知数是每一项的系数）至少要有n个方程才能有唯一解。（线代可以证明，有兴趣自己查。）那么，如果我们知道函数的n个不同的值。即n个，我们就可以唯一的确定一个多项式。DFT就是巧妙的利用复数，将n个系数快速的转换为对应的n个点【】。

系数法：系数法就是用来表示多项式。IDFT就是巧妙的利用复数，将n个点快速的转换为对应的n个系数【】。

二、模板

以luogu 3803的模板题为例，用的kuangbin大神（没时间手敲了）的板子。

其中极坐标(r,i)，对应直角坐标系(x,y)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
const double PI = acos(-1.0);
struct Complex
{
    double r,i;
    Complex(double _r = 0,double _i = 0)
    {
        r = _r; i = _i;
    }
    Complex operator +(const Complex &b)
    {
        return Complex(r+b.r,i+b.i);
    }
    Complex operator -(const Complex &b)
    {
        return Complex(r-b.r,i-b.i);
    }
    Complex operator *(const Complex &b)
    {
        return Complex(r*b.r-i*b.i,r*b.i+i*b.r);
    }
};
void change(Complex* y,int len)
{
    int i,j,k;
    for(i = 1, j = len/2;i < len-1;i++)
    {
        if(i < j)swap(y[i],y[j]);
        k = len/2;
        while( j >= k)
        {
            j -= k;
            k /= 2;
        }
        if(j < k)j += k;
    }
}
void fft(Complex* y,int len,int on)
{
    change(y,len);
    for(int h = 2;h <= len;h <<= 1)
    {
        Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for(int j = 0;j < len;j += h)
        {
            Complex w(1,0);
            for(int k = j;k < j+h/2;k++)
            {
                Complex u = y[k];
                Complex t = w*y[k+h/2];
                y[k] = u+t;
                y[k+h/2] = u-t;
                w = w*wn;
            }
        }
    }
    if(on == -1)
        for(int i = 0;i < len;i++)
            y[i].r /= len;
}
Complex x1[N<<2];
Complex x2[N<<2];
int n,m,a[N],b[N];
int num[N<<1]; 
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<=m;i++)
		scanf("%d",&b[i]);
	int len,len1;
	//len1=n+m+1;
	len=1;
	while(len < ((n+1)<<1) || len < ((m+1)<<1)) len <<= 1;
	for(int i = 0; i <= n; i++)
	   x1[i] = Complex(a[i],0);
	for(int i = n+1; i < len; i++)
	   x1[i] = Complex(0,0);
	for(int i = 0; i <= m; i++)
	   x2[i] = Complex(b[i],0);
	for(int i = m+1; i < len; i++)
	   x2[i] = Complex(0,0);
	fft(x1,len,1);
	fft(x2,len,1);
	for(int i = 0;i < len;i++)
            x1[i] = (x1[i]*x2[i]);
	fft(x1,len,-1);	
    for(int i = 0;i <= n+m;i++)
        num[i] = (x1[i].r+0.5);	
	for(int i=0;i<=n+m;i++)
		printf("%d%c",num[i],i==n+m?'\n':' ');
	
	return 0;	
} 

三、例题

1、luogu P3803 【模板】多项式乘法（FFT）      题解 

2、luogu P1919 【模板】A*B Problem升级版（FFT快速傅里叶）      题解 

3、HDU - 1402 A * B Problem Plus       题解

4、石油大 2020年秋季组队训练赛第二十五场 问题 H: Needle      题解

5、HDU - 4609 3-idiots      题解

 

强推大佬博客

 

现在时间是2021-2-2，重新回来看2019学习的一知半解的$FFT$，又有了新的理解

所以修改了以往写过的文章，并增添些许内容

因为过去一年多，上了高中，学的知识多了些，以前不懂的有些东西现在看来挺简单的？？

Add

建议了解系数和点值表示法后直接从复数看起

因为前面很多是第一次学习的时候，为了全面了解

然而似乎并没有起到这个效果？？

文章目录
引入
系数和点值表示法
系数表示法
概念
系数表示法$\rightarrow$点值表示法
系数表示法的优缺点
点值表示法
概念
点值表达式-->系数表达式
点值表达式的优缺点
复数和单位复根
复数
单位复根
傅里叶正变换（一般形式$\rightarrow$点值表达式）
理论
递归模板
傅里叶逆变换（点值表达式-->一般形式）
离散傅里叶变换实现
理论
模板
模板的板题运用
例题：洛谷P3803【模板】多项式乘法（FFT）
递归版CODE
迭代版CODE

引入
如果给你一个多项式 $A(x) = ∑a_nx^n$ 和 $B(x) = ∑b_nx^n$，求 $A(x) · B(x)$

你会怎么做？？

——可能只能选择$O(n^2)$，做$\sum_{i=1}^n\sum_{j=1}^mai*bj$

但是你觉得那些毒瘤出题dalao，会让你轻轻松松$O(n^2)$水过去吗？



如此之高的时间复杂度永远成为了多项式乘法的一个瓶颈…

直到伟大的$FFT$就出现了，将其优化到$O(nlogn)$

系数和点值表示法
对于求一个$n-1$次的多项式$f(x)$，可以有两种表示方法，并且可以互相转化
系数表示法
概念
$f(x)=\sum_{i=0}^{n-1}c_i*x^i$

什么意思呢？

🍔设$f(x)=(a_0*x^0+a_1*x^1+a_2*x^2)*(b_0*x^0+b_1*x^1+b_2*x^2)$
那么一一相乘将之拆成了九项式子相加

$f(x)=a_0b_0*x^0+a_0b_1*x^1+a_0b_2*x^2+a_1b_0*x^1+a_1b_1*x^2$

$+a_1b_2*x^3+a_2b_0*x^2+a_2b_1*x^3+a_2b_2*x^4$
进行同类项合并

$f(x)=a_0b_0*x^0+(a_0b_1+a_1b_0)*x_1+(a_0b_2+a_1b_1+a_2b_0)*x^2$

$+(a_1b_2+a_2b_1)*x^3+a_2b_2*x^4$
$c_0=a_0b_0$

$c_1=(a_0b_1+a_1b_0)$

$c_2=(a_0b_2+a_1b_1+a_2b_0)$

$c_3=(a_1b_2+a_2b_1)$

$c_4=a_2b_2$
用中国话来理解就是$c_i$是我们整合后的对于$x^i$的系数和，将这些相加就是最后的$f(x)$


Add

$c_i$本质来说可以看作是两个函数的卷积

$h(n)=\sum_{i=0}^{n-1}c_i\ x^i,f(n)=\sum_{i=0}^{n-1}a_i\ x^i,g(n)=\sum_{i=0}^{n-1}b_i\ x^i$$\Rightarrow c_i=\sum_{j=0}^ia_j\times b_{i-j}$


系数表示法$\rightarrow$点值表示法
就是把$x_i$带进去就可以算出来每一个点$i$的函数值，就可以表示该点$(x_i,y_i)$

$y_i=\sum_{j=0}^{n-1}c_j*x_i^j$
系数表示法的优缺点
优点

多项式的求值计算效率高，对于$A(x)=a_0+a_1*x^1+a_2*x^2...a_n*x^n$

提一个同类项$x$，变成

$A(x)=a_0+x(a_1+a_2*x+...a_n*x^{n-1})$，不停地提$x$出来

我们就可以在$a_0$处通过霍纳法则$O(n)$算出来
多项式的加减计算效率也高

$A(x)=a_0+a_1*x^1+a_2*x^2+...+a_{n-1}*x^{n-1}$

$B(x)=b_0+b_1*x^1+...+b_{n-1}*x^{n-1}$

可以通过$O(n)$，算出$C(x)=c_0+c_1*x^1+...+c_{n-1}*x^{n-1}$

对于每一个$i∈[0,n)$，都有$c_i=a_i+b_i$，其实就是直接系数方面的相加减
缺点

多项式的乘法计算时间复杂度将达到$O(n^2)$

1.感性理解就是我们要枚举$A$里面的每一项，再与$B$里面的每一项进行相乘再合并同类项

2.数学公式表达则是：解释一下为什么上界是$2n-2$

额其实很好想，$A,B$的最高项都是$x^{n-1}$相乘肯定就是$C$的最高项，也就是$x^{2n-2}$

$C(x)=\sum_{i=0}^{2n-2}c_i*x^i,c_i=\sum_{j=0}^ia_jb_{i-j}$
点值表示法
概念
给一堆点对$(x_1,x_2,x_3...x_n),(y_1,y_2,y_3...y_n)$，满足$f(x_i)=y_i$

即$(x_i,y_i)$是曲线上$y=f(x)$的点


Add

这样表示似乎更好？

$(x_0,y_0),(x_1,y_1),(x_2,y_2)....(x_{n-1},y_{n-1})$


用中国话来讲就是我们知道了平面直角坐标系上某条函数的$n$对点

然后就可以勾勒出这一条唯一的函数图象
要确定一条函数的图像，要至少知道函数最高次+1个不同的点
简单证明一下：

1.感性理解，我们说两个点确定一条直线，也就是说要两个点才能画出一次函数

而我们的抛物线又要三个点才能画出二次函数$...$以此类推

2.运用解方程的方法，我们面对四个点会设$f(x)=a*x^3+b*x^2+c*x^1+d$

四个不同的方程对应四个解

感觉好像是一样的证明，别管这么多了，反正都是简单证明，口胡口胡
点值表达式–>系数表达式
$f(x)=\sum_{i=0}^{n-1}y_i\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}$

这个证明要用到拉格朗日插值法，但是因为我们一般不用这玩意儿，老子就不搞了，太现实了
点值表达式的优缺点
优点

加减法计算效率高：对两个点值表达的次数界为$n$的多项式，计算只有$O(n)$

如果$C(x)=A(x)+b(x)$，那么$C(x_k)=A(x_k)+B(x_k)$
更具体而言：对于给定的$A{(x_0,y_0),(x_1,y_1)...(x_{n-1},y_{n-1}))},B{(x_0,y_0'),(x_1,y_1')...(x_{n-1},y_{n-1}'))}$

那么$A$和$B$对相同的$n$个点对求和，$C$的点对就表示成$C{(x_0,y_0+y_0'),(x_1,y_1+y_1')...(x_{n-1},y_{n-1}+y_{n-1}'))}$
乘法计算效率也高：对两个点值表达的次数界为$n$的多项式，计算只有$O(n)$

如果$C(x)=A(x)*b(x)$，那么$C(x_k)=A(x_k)*B(x_k)$

这样只需要将$A,B$进行逐点相乘就可以求出了$C$，但是$C$的次数界要达到$2n$

$A,B$次数界也只有$n$，所以我们必须对$A,B$进行扩点处理，将其扩大成$C$的次数界
更具体而言：扩充$A{(x_0,y_0),(x_1,y_1)...(x_{2n-1},y_{2n-1}))},B{(x_0,y_0'),(x_1,y_1')...(x_{2n-1},y_{2n-1}'))}$

$C$的点对就表示成$C{(x_0,y_0+y_0'),(x_1,y_1+y_1')...(x_{n-1},y_{2n-1}+y_{2n-1}'))}$
缺点

我们如何求一个新点的值呢？是不是只能转化成系数表达式，用$O(n)$计算

但是时间复杂度就在转化这里达到了$O(n^2)$
换言之：对于多项式 $A(x)$ 和 $B(x)$，假设 $degA + degB < n$（

deg是数学中的表示多项式的次数的玩意儿）

如果有 $A$ 和 $B$ 在 ${x_0, x_1, . . . , x_{n-1}}$ 处的点值表示

则 $(A · B)$的点值表示可以通过$(A · B)(x_i) = A(x_i) · B(x_i)$ 在 $O(N)$ 时间内得到

还原 $(A · B)$ 为系数表示就实现了多项式乘法，但是还原的时间$O(n^2)$
🍔：所以如果有一道题给我们系数表达式，最后又让我们输出结果的系数表达式

我们用以上的方法虽然计算成点值表达式只用了$O(n)$

但是最后在转化成系数表达式的时候，时间复杂度还是蹭蹭蹭地涨到了$O(n^2)$

看上面的式子，我们会面临枚举$i,j$的难题，还是没有在本质上解决问题

但是我们的$FFT$就剋以做到以上的转化且只用$O(nlogn)$

1.把已知的一个多项式转化成对应的点值表示

2.把已知的点值表示转换成对应的多项式

说了这么多，还是没有告诉我怎么做啊！！！不急慢慢往下看



复数和单位复根

复数

我们把形如$z=a+bi$（a,b均为实数）的数称为复数，其中$a$称为实部，$b$称为虚部，$i$称为虚数单位

$i=\sqrt{-1}$，即$i^2=-1$

我们可以把复数当做一个向量丢在二维平面，即平面直角坐标系



百度百科说：复数之间的加减乘（除）是可以直接算的，除法因为不怎么用就不说了



1.加法法则

设$z1=a+bi，z2=c+di$是任意两个复数，

则它们的和是 $(a+bi)+(c+di)=(a+c)+(b+d)i$

两个复数的和依然是复数，它的实部是原来两个复数实部的和，它的虚部是原来两个虚部的和，当然复数的加法满足交换律和结合律

2.减法法则

设$z1=a+bi，z2=c+di$是任意两个复数，

则它们的差是 $(a+bi)-(c+di)=(a-c)+(b-d)i$

两个复数的差依然是复数，它的实部是原来两个复数实部的差，它的虚部是原来两个虚部的差

3.乘法法则

设$z1=a+bi，z2=c+di(a、b、c、d∈R)$是任意两个复数，

那么它们的积$(a+bi)(c+di)=(ac-bd)+(bc+ad)i$

其实就是把两个复数相乘，类似两个多项式相乘，展开得: $ac+adi+bci+bdi^2$，因为$i^2=-1$，所以结果是$(ac－bd)+(bc+ad)i$ ，两个复数的积仍然是一个复数

此时，复数相乘表现为幅角相加，模长相乘
单位复根
定义$n$次单位复根为$\omega_n^i$，满足$x^n=1$的复数$x$，表现在平面直角坐标系中


单位复根满足的性质如下：可以想象成在单位圆上的旋转

$\omega_n^a*\omega_n^b=\omega_n^{a+b}$

$\omega_n^i=\omega_n^{i+n}$，也就是转了一圈单位圆最后在坐标系上只转了幅角为i

$\omega_{kn}^{ki}=\omega_n^i$

$\omega_n^i=-\omega_n^{i+n/2}$，$-$可以理解为倒着转

因为单位复根刚好有$n$个，可以分别一一对应我们的$n-1$次多项式，形成点值表达式
$\{(\omega_n^0,f(\omega_n^0)),(\omega_n^1,f(\omega_n^1)),(\omega_n^2,f(\omega_n^2))...,(\omega_n^{n-1},f(\omega_n^{n-1}))\}$


我们的$FFT$是要求$n$为2的幂次的


Add

对于一个函数$f(n)=\sum_{i=0}^{n-1}c_i\ x_i$

其实可以上调$n$但不能下降$n$

意思就是可以将$n$配成任何比$n$大的$n'$，系数$c$直接配成$0$，不就行了？

所以$FFT$的$n$的要求是完全可以人为调控达到的


所以像上图的五个单位复根

其实我们是分成了八个单位复根，然后就只用前五个

如图分成了八份，只用其中涂绿了的五份




Add

前面提到是将复数当成向量放在二维平面的单位圆里

所以对于单位圆上的一点，假设角度为$x$，那么该点可以表示为$(cos\ x,i\ sin\ x)$

对于两个角度分别为$x,y$的在单位圆上的点，相乘

$(cos\ x,i\ sin\ x)\times (cos\ y,i\ sin\ y)=$

$(cos\ x\ cos\ y-sin\ x\ sin\ y,i(sin\ x\ cos\ y+cos\ x\ sin\ y))$

发现就是角度为$x+y$的点坐标$(cos(x+y),i\ sin(x+y))$

这也恰恰应证了复数相乘表现为幅角相加，模长相乘

点乘算出来的结果是一个点

叉乘算出来的结果仍是一个向量


傅里叶正变换（一般形式$\rightarrow$点值表达式）
理论


Add

$FFT$就是知道用点值表达式表示函数


FFT 的正变换实现，是基于对多项式进行奇偶项分开递归再合并的分治进行的

对于 $n-1$ 次多项式，我们选择插入 $n$ 次单位根求出其点值表达式，

这就跟我们引入单位复根的原因相结合了
设$f(x)=a_0+a_1*x^1+a_2*x^2+...+a_{n-1}*x^{n-1}$，

$f_0(x)=a_0+a_2*x+a_4*x^2+a_6*x^3+...$，$f_1(x)=a_1+a_3*x+a_5*x^2+...$

则$f(x)=f_0(x^2)+x*f_1(x^2)$

证明的话把这个式子展开就行了，跳过
也就是说我们把$f(x)$分成了两类，奇数项分成一类，偶数项分成一类，去得到上列公式
接着，令$n=2*p$，那么就有以下转化

$f(\omega_n^i)=f_0((\omega_{n/2}^{i/2})^2)+\omega_n^i*f1((w_{n/2}^{i/2})^2)=f_0(\omega_p^i)+\omega_n^i*f_1(\omega_p^i)$

$f(\omega_n^{i+p})=f_0((\omega_{n/2}^{(i+p)/2})^2)+\omega_n^{i+p}*f1((w_{n/2}^{(i+p)/2})^2)$$=f_0(\omega_p^{i+p})+\omega_n^{i+p}*f_1(\omega_p^{i+p})=f_0(\omega_p^i)-\omega_n^i*f_1(\omega_p^i)$



由上述式子我们可以知道，如果我们知道$f_0(\omega_p^i),f_1(\omega_p^i)$，我们就可以$O(1)$算出$f(\omega_n^i),f(\omega_n^{i+n/2})$

那么如果我们递归求出了$f_0(x),f_1(x)$的$n/2$次的插值，我们就能$O(n)$的算出$f(x)$的$n$次单位根的插值，所以时间复杂度则是$O(nlogn)$
一言以蔽之：当 $x$ 取遍所有 $n$ 次单位复根时，$x^2$ 取遍所有 $(n/2)$ 次单位复根
递归模板
struct complex {//先自己手打STL里面的复数，可以防止某些**卡常
	double real, i;
	complex () {}
	complex ( double xx, double yy ) {
		real = xx;
		i = yy;
	}
}a[MAXN], b[MAXN];

complex operator + ( complex s, complex t ) {
	return complex ( s.real + t.real, s.i + t.i );
}
complex operator - ( complex s, complex t ) {
	return complex ( s.real - t.real, s.i - t.i );
}
complex operator * ( complex s, complex t ) {
	return complex ( s.real * t.real - s.i * t.i, s.real * t.i + s.i * t.real );
}

const double pi = acos ( -1.0 );

void FFT ( int limit, complex *a, int inv ) {
	if ( limit == 1 )
		return;
	complex a1[limit >> 1], a2[limit >> 1];
	for ( int i = 0;i < limit;i += 2 ) {
		a1[i >> 1] = a[i];
		a2[i >> 1] = a[i + 1];
	}
	FFT ( limit >> 1, a1, inv );
	FFT ( limit >> 1, a2, inv );
	complex w = complex ( cos ( 2 * pi / limit ), inv * sin ( 2 * pi / limit ) ), p = complex ( 1, 0 );
	for ( int i = 0;i < ( limit >> 1 );i ++, p = p * w ) {
		a[i] = a1[i] + p * a2[i];
		a[i + ( limit >> 1)] = a1[i] - p * a2[i];
	}
}


傅里叶逆变换（点值表达式–>一般形式）
其实正变换的实现就是下列的矩阵相乘，反正我是没看出来

$\begin{bmatrix} 
\ (\omega_n^0)^0 & (\omega_n^0)^1 & ... &(\omega_n^0)^{n-1} \\
\\ (\omega_n^1)^0 &  (\omega_n^1)^1 & ... & (\omega_n^1)^{n-1} \\
\\.&.&...&.
\\.&.&...&.
\\ (\omega_n^{n-1})^0 &  (\omega_n^{n-1})^1 & ... & (\omega_n^{n-1})^{n-1} \\
\end{bmatrix} \times \begin{bmatrix}
\ a_0 \\
\ a_1\\
\ a_2 \\
\ .\\
\ .\\
\ .\\
\ a_{n-1}
\end{bmatrix} = \begin{bmatrix}
\ f(w_n^0) \\
\ f(w_n^1) \\
\ f(w_n^2)\\
\ . \\
\ . \\
\ . \\
\ f(w_n^{n-1}) \\
\end{bmatrix}$


Add

快速傅里叶逆变化$IFFT$，将点值表达式转换为系数表达式

一般都是用的系数表达式


矩阵相乘的第i行第j列等于

求和第一个矩阵的第i行的每一个数和第二个矩阵的第j列的每一个数的乘积
我们记$V$就为（系数矩阵）上列的第一个矩阵，接下来再定义一个矩阵$D$，

$D=
\begin{bmatrix} 
\ (\omega_n^{-0})^0 & (\omega_n^{-0})^1 & ... &(\omega_n^{-0})^{n-1} \\
\\ (\omega_n^{-1})^0 &  (\omega_n^{-1})^1 & ... & (\omega_n^{-1})^{n-1} \\
\\.&.&...&.
\\.&.&...&.
\\ (\omega_n^{-n+1})^0 &  (\omega_n^{-n+1})^1 & ... & (\omega_n^{-n+1})^{n-1} \\
\end{bmatrix}$



那么计算矩阵$D*V$的$i,j$项，分为两种情况

①：$i=j$，(任何数除零外的零次方都为1)

$(D*V)_{i,j}=\sum_{k=0}^{n-1}D_{i,k}*V_{k,j}=\sum_{k=0}^{n-1}\omega_n^{-ik}*\omega_n^{jk}=\sum_{k=0}^{n-1}\omega_n^{(j-i)k}=\sum_{k=0}^{n-1}\omega_n^0=n$

②：$i\ne j$

$(D*V)_{i,j}=\sum_{k=0}^{n-1}D_{i,k}*V_{k,j}=\sum_{k=0}^{n-1}\omega_n^{-ik}*\omega_n^{jk}=\sum_{k=0}^{n-1}\omega_n^{(j-i)k}$

$=(\omega_n^{j-i})^0+(\omega_n^{j-i})^1+(\omega_n^{j-i})^2+...+(\omega_n^{j-i})^{n-1}$

发现这个公式是一个以$\omega_n^{j-1}$为公比的等比数列，





那么就可以转换为

$\frac{(\omega_n^{j-i})^0-(\omega_n^{j-i})^1*(\omega_n^{j-i})^{n-1}}{1-(\omega_n^{j-i})^1}=\frac{1-(\omega_n^{j-i})^n}{1-\omega_n^{j-i}}=\frac{0}{1-\omega_n^{j-i}}=0$

单位复根的$n$次方$=0$，见上文单位复根定义

因为此公式的前提是$j\ne i$，所以分母一定不为$0$
故$j\ne i$时，$(D*V)_{i,j}=0$

用$D*V*f$去转换为点值表达式，去带最上面的这一板块的公式，你会惊讶地发现

$\begin{bmatrix} 
\ (\omega_n^{-0})^0 & (\omega_n^{-0})^1 & ... &(\omega_n^{-0})^{n-1} \\
\\ (\omega_n^{-1})^0 &  (\omega_n^{-1})^1 & ... & (\omega_n^{-1})^{n-1} \\
\\.&.&...&.
\\.&.&...&.
\\ (\omega_n^{-n+1})^0 &  (\omega_n^{-n+1})^1 & ... & (\omega_n^{-n+1})^{n-1} \\
\end{bmatrix} \times
\begin{bmatrix} 
\ (\omega_n^0)^0 & (\omega_n^0)^1 & ... &(\omega_n^0)^{n-1} \\
\\ (\omega_n^1)^0 &  (\omega_n^1)^1 & ... & (\omega_n^1)^{n-1} \\
\\.&.&...&.
\\.&.&...&.
\\ (\omega_n^{n-1})^0 &  (\omega_n^{n-1})^1 & ... & (\omega_n^{n-1})^{n-1} \\
\end{bmatrix} \times \begin{bmatrix}
\ f(w_n^0) \\
\ f(w_n^1) \\
\ f(w_n^2)\\
\ . \\
\ . \\
\ . \\
\ f(w_n^{n-1}) \\
\end{bmatrix} =$

$\begin{bmatrix}
\ n&0&0&...&0 \\
\ 0&n&0&...&0 \\
\ 0 &0&n&..&0\\
\ ...&...&...&... &0\\
\ 0&0&0&...&n \\
\end{bmatrix} \times \begin{bmatrix}
\ f(w_n^0) \\
\ f(w_n^1) \\
\ f(w_n^2)\\
\ . \\
\ . \\
\ . \\
\ f(w_n^{n-1}) \\
\end{bmatrix} =
\begin{bmatrix}
\ n*a_0 \\
\ n*a_1\\
\ n*a_2 \\
\ .\\
\ .\\
\ .\\
\ n*a_{n-1}
\end{bmatrix}$

所以最后对答案全部$/n$就是点值表达式了，这也是为什么我们为这么定义$D,V$了

逆变换就相当于把正变换过程中的$\omega^k_n$换成$w^{-k}_n$，之后结果除以n就可以了——摘自某dalao博客


离散傅里叶变换实现

理论
之前的思路全都是递归思想，实现出来后发现吓死个人，所以我们考虑转成迭代

以下的图摘自学长大佬：



学长让我们换成二进制看看：



可以发现终序列是原序列每个元素的翻转。

于是我们可以先把要变换的系数排在相邻位置，从下往上迭代。

在这里给出一个参考的方法：

我们对于每个 i，假设已知 i-1 的翻转为 j。考虑不进行翻转的二进制加法怎么进行：从最低位开始，找到第一个为 0 的二进制位，将它之前的 1 变为 0，将它自己变为 1。因此我们可以从 j 的最高位开始，倒过来进行这个过程

——摘自某dalao的博主

所以我们才会把这个$FFT$跟蝴蝶操作搞在一起，盗一波百度的图片


模板
void FFT ( complex *c, int f ) {
	for ( int i = 0;i < len;i ++ )
		if ( i < r[i] )
			swap ( c[i], c[r[i]] );
	for ( int i = 1;i < len;i <<= 1 ) {
		complex omega ( cos ( pi / i ), f * sin ( pi / i ) );
		for ( int j = 0;j < len;j += ( i << 1 ) ) {
			complex w ( 1, 0 );
			for ( int k = 0;k < i;k ++, w = w * omega ) {
				complex x = c[j + k], y = w * c[j + k + i];
				c[j + k] = x + y;
				c[i + j + k] = x - y;
			}
		}
	}
}


模板的板题运用
例题：洛谷P3803【模板】多项式乘法（FFT）
题目
递归版CODE
#include <cmath>
#include <cstdio>
using namespace std;
#define MAXN 3000005
struct complex {
	double real, i;
	complex () {}
	complex ( double xx, double yy ) {
		real = xx;
		i = yy;
	}
}a[MAXN], b[MAXN];

complex operator + ( complex s, complex t ) {
	return complex ( s.real + t.real, s.i + t.i );
}
complex operator - ( complex s, complex t ) {
	return complex ( s.real - t.real, s.i - t.i );
}
complex operator * ( complex s, complex t ) {
	return complex ( s.real * t.real - s.i * t.i, s.real * t.i + s.i * t.real );
}

const double pi = acos ( -1.0 );

void FFT ( int limit, complex *a, int inv ) {
	if ( limit == 1 )
		return;
	complex a1[limit >> 1], a2[limit >> 1];
	for ( int i = 0;i < limit;i += 2 ) {
		a1[i >> 1] = a[i];
		a2[i >> 1] = a[i + 1];
	}
	FFT ( limit >> 1, a1, inv );
	FFT ( limit >> 1, a2, inv );
	complex w = complex ( cos ( 2 * pi / limit ), inv * sin ( 2 * pi / limit ) ), p = complex ( 1, 0 );
	for ( int i = 0;i < ( limit >> 1 );i ++, p = p * w ) {
		a[i] = a1[i] + p * a2[i];
		a[i + ( limit >> 1)] = a1[i] - p * a2[i];
	}
}

int main() {
	int n, m;
	scanf ( "%d %d", &n, &m );
	for ( int i = 0;i <= n;i ++ )
		scanf ( "%lf", &a[i].real );
	for ( int i = 0;i <= m;i ++ )
		scanf ( "%lf", &b[i].real );
	int limit = 1;
	while ( limit <= n + m )
		limit <<= 1; 
	FFT ( limit, a, 1 );
	FFT ( limit, b, 1 );
	for ( int i = 0;i <= limit;i ++ )
		a[i] = a[i] * b[i];
	FFT ( limit, a, -1 );
	for ( int i = 0;i <= n + m;i ++ )
		printf ( "%d ", ( int ) ( a[i].real / limit + 0.5 ) );
	return 0;
}

迭代版CODE
推荐使用递推版，要比递归版快
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define maxn 3000005
struct complex {
	double x, i;
	complex(){}
	complex( double X, double I ) {
		x = X, i = I;
	}
}A[maxn], B[maxn];
int len = 1;
int r[maxn];

double pi = acos( -1.0 );

complex operator + ( complex a, complex b ) {
	return complex( a.x + b.x, a.i + b.i );
}

complex operator - ( complex a, complex b ) {
	return complex( a.x - b.x, a.i - b.i );
}

complex operator * ( complex a, complex b ) {
	return complex( a.x * b.x - a.i * b.i, a.x * b.i + a.i * b.x );
}

void FFT( complex *c, int f ) { //f=1系数转化为点值表达式w^1  f=-1点值转化为系数表达式w^(-1)
/*
蝴蝶发现：终序列是原序列每个元素二进制的翻转 
*/ 
	for( int i = 0;i < len;i ++ )
		if( i < r[i] ) swap( c[i], c[r[i]] ); 
	for( int i = 1;i < len;i <<= 1 ) { //枚举迭代区间长度的一半 
		complex omega( cos( pi / i ), f * sin( pi / i ) );//区间长度本来是2i 就是要分成2i份 每一份是2pi/2i=pi/i 
		for( int j = 0;j < len;j += ( i << 1 ) ) {//枚举每一次迭代区间的开头
			complex w( 1, 0 );
			for( int k = 0;k < i;k ++, w = w * omega ) {
/*
只枚举迭代区间的左半部分
左半部分和右半部分进行计算
就可以算出上一层 直接覆盖即可
(w^k)^2=[w^(k+n/2)]^2 
左半部分是按照偶数分类
右半部分是按照奇数分类
f(x)=x*f1(x^2)+f2(x^2)
f1是奇数分类 f2是偶数分类 
*/ 
				complex x = c[j + k], y = w * c[j + k + i];
				c[j + k] = x + y;
				c[j + k + i] = x - y;
			}
		}
	}
}

int main() {
	int n, m;
	scanf( "%d %d", &n, &m );
	for( int i = 0;i <= n;i ++ )
		scanf( "%lf", &A[i].x );
	for( int i = 0;i <= m;i ++ )
		scanf( "%lf", &B[i].x );
	int l = 0;
	while( len <= n + m ) {
		len <<= 1;
		l ++;
	}
	for( int i = 0;i < len;i ++ )
		r[i] = ( r[i >> 1] >> 1 ) | ( ( i & 1 ) << ( l - 1 ) );
/*
在原序列中i与i/2的关系是:i可以看做是i/2的二进制上的每一位左移一位得来
那么在反转后的数组中就需要右移一位
因为i直接左移一位
那么i二进制的右边第一位是没有考虑到的
那么如果那一位是1
反转后就应该是最高位为1 
*/
	FFT( A, 1 ); 
	FFT( B, 1 );
	for( int i = 0;i < len;i ++ )
		A[i] = A[i] * B[i];
	FFT( A, -1 );
	for( int i = 0;i <= n + m;i ++ )
		printf( "%d ", int( A[i].x / len + 0.5 ) );
	return 0;
}



给个版权吧：以上内容部分学习于

https://www.cnblogs.com/Tiw-Air-OAO/p/10162034.html

学校的lucky学长（没找到blog）

老师专讲

叉姐

	

链接：
Python小例子：https://github.com/jackzhenguo/python-small-examples
贡献
欢迎贡献小例子到此库
License
允许按照要求转载，但禁止用于任何商用目的。
小例子
一、 数字
1 求绝对值
绝对值或复数的模
In [1]: abs(-6)Out[1]: 6
2 进制转化
十进制转换为二进制：
In [2]: bin(10)Out[2]: '0b1010'
十进制转换为八进制：
In [3]: oct(9)Out[3]: '0o11'
十进制转换为十六进制：
In [4]: hex(15)Out[4]: '0xf'
3 整数和ASCII互转
十进制整数对应的ASCII字符
In [1]: chr(65)Out[1]: 'A'
查看某个ASCII字符对应的十进制数
In [1]: ord('A')Out[1]: 65
4 元素都为真检查
所有元素都为真，返回 True，否则为False
In [5]: all([1,0,3,6])Out[5]: False
In [6]: all([1,2,3])Out[6]: True
5 元素至少一个为真检查　
至少有一个元素为真返回True，否则False
In [7]: any([0,0,0,[]])Out[7]: False
In [8]: any([0,0,1])Out[8]: True
6 判断是真是假　　
测试一个对象是True, 还是False.
In [9]: bool([0,0,0])Out[9]: TrueIn [10]: bool([])Out[10]: FalseIn [11]: bool([1,0,1])Out[11]: True
7 创建复数
创建一个复数
In [1]: complex(1,2)Out[1]: (1+2j)
8 取商和余数　　
分别取商和余数
In [1]: divmod(10,3)Out[1]: (3, 1)
9 转为浮点类型　
将一个整数或数值型字符串转换为浮点数
In [1]: float(3)Out[1]: 3.0
如果不能转化为浮点数，则会报ValueError:
In [2]: float('a')# ValueError: could not convert string to float: 'a'
10 转为整型　　
int(x, base =10) , x可能为字符串或数值，将x 转换为一个普通整数。如果参数是字符串，那么它可能包含符号和小数点。如果超出了普通整数的表示范围，一个长整数被返回。
In [1]: int('12',16)Out[1]: 18
11 次幂
base为底的exp次幂，如果mod给出，取余
In [1]: pow(3, 2, 4)Out[1]: 1
12 四舍五入
四舍五入，ndigits代表小数点后保留几位：
In [11]: round(10.0222222, 3)Out[11]: 10.022In [12]: round(10.05,1)Out[12]: 10.1
13 链式比较
i = 3print(1 < i < 3)  # Falseprint(1 < i <= 3)  # True
二、 字符串
14 字符串转字节　　
字符串转换为字节类型
In [12]: s = "apple"                                                            In [13]: bytes(s,encoding='utf-8')Out[13]: b'apple'
15 任意对象转为字符串　　
In [14]: i = 100                                                                In [15]: str(i)Out[15]: '100'In [16]: str([])Out[16]: '[]'In [17]: str(tuple())Out[17]: '()'
16 执行字符串表示的代码
将字符串编译成python能识别或可执行的代码，也可以将文字读成字符串再编译。
In [1]: s  = "print('helloworld')"In [2]: r = compile(s,"", "exec")In [3]: rOut[3]: <code object <module> at 0x0000000005DE75D0, file "", line 1>In [4]: exec(r)
helloworld
17 计算表达式
将字符串str 当成有效的表达式来求值并返回计算结果取出字符串中内容
In [1]: s = "1 + 3 +5"
    ...: eval(s)
    ...:Out[1]: 9
18 字符串格式化　
格式化输出字符串，format(value, format_spec)实质上是调用了value的__format__(format_spec)方法。
In [104]: print("i am {0},age{1}".format("tom",18))
i am tom,age18
3.1415926
{:.2f}
3.14
保留小数点后两位
3.1415926
{:+.2f}
+3.14
带符号保留小数点后两位
-1
{:+.2f}
-1.00
带符号保留小数点后两位
2.71828
{:.0f}
3
不带小数
5
{:0>2d}
05
数字补零 (填充左边, 宽度为2)
5
{:x<4d}
5xxx
数字补x (填充右边, 宽度为4)
10
{:x<4d}
10xx
数字补x (填充右边, 宽度为4)
1000000
{:,}
1,000,000
以逗号分隔的数字格式
0.25
{:.2%}
25.00%
百分比格式
1000000000
{:.2e}
1.00e+09
指数记法
18
{:>10d}
' 18'
右对齐 (默认, 宽度为10)
18
{:<10d}
'18 '
左对齐 (宽度为10)
18
{:^10d}
' 18 '
中间对齐 (宽度为10)
三、 函数
19 拿来就用的排序函数
排序：
In [1]: a = [1,4,2,3,1]In [2]: sorted(a,reverse=True)Out[2]: [4, 3, 2, 1, 1]In [3]: a = [{'name':'xiaoming','age':18,'gender':'male'},{'name':'     ...: xiaohong','age':20,'gender':'female'}]In [4]: sorted(a,key=lambda x: x['age'],reverse=False)Out[4]:
[{'name': 'xiaoming', 'age': 18, 'gender': 'male'},
 {'name': 'xiaohong', 'age': 20, 'gender': 'female'}]
20 求和函数
求和：
In [181]: a = [1,4,2,3,1]In [182]: sum(a)Out[182]: 11In [185]: sum(a,10) #求和的初始值为10Out[185]: 21
21 nonlocal用于内嵌函数中
关键词nonlocal常用于函数嵌套中，声明变量i为非局部变量；如果不声明，i+=1表明i为函数wrapper内的局部变量，因为在i+=1引用(reference)时,i未被声明，所以会报unreferenced variable的错误。
def excepter(f):
    i = 0
    t1 = time.time()def wrapper():try:f()except Exception as e:nonlocal i
            i += 1print(f'{e.args[0]}: {i}')
            t2 = time.time()if i == n:print(f'spending time:{round(t2-t1,2)}')return wrapper
22 global 声明全局变量
先回答为什么要有global，一个变量被多个函数引用，想让全局变量被所有函数共享。有的伙伴可能会想这还不简单，这样写：
i = 5def f():print(i)def g():print(i)passf()g()
f和g两个函数都能共享变量i，程序没有报错，所以他们依然不明白为什么要用global.
但是，如果我想要有个函数对i递增，这样：
def h():
    i += 1h()
此时执行程序，bang, 出错了！抛出异常：UnboundLocalError，原来编译器在解释i+=1时会把i解析为函数h()内的局部变量，很显然在此函数内，编译器找不到对变量i的定义，所以会报错。
global就是为解决此问题而被提出，在函数h内，显式地告诉编译器i为全局变量，然后编译器会在函数外面寻找i的定义，执行完i+=1后，i还为全局变量，值加1：
i = 0def h():global i
    i += 1h()print(i)
23 交换两元素
def swap(a, b):return b, aprint(swap(1, 0))  # (0,1)
24 操作函数对象
In [31]: def f():
    ...:     print('i\'m f')
    ...:In [32]: def g():
    ...:     print('i\'m g')
    ...:In [33]: [f,g][1]()
i'm g
创建函数对象的list，根据想要调用的index，方便统一调用。
25 生成逆序序列
list(range(10,-1,-1)) # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
第三个参数为负时，表示从第一个参数开始递减，终止到第二个参数(不包括此边界)
26 函数的五类参数使用例子
python五类参数：位置参数，关键字参数，默认参数，可变位置或关键字参数的使用。
def f(a,*b,c=10,**d):print(f'a:{a},b:{b},c:{c},d:{d}')
默认参数c不能位于可变关键字参数d后.
调用f:
In [10]: f(1,2,5,width=10,height=20)
a:1,b:(2, 5),c:10,d:{'width': 10, 'height': 20}
可变位置参数b实参后被解析为元组(2,5);而c取得默认值10; d被解析为字典.
再次调用f:
In [11]: f(a=1,c=12)
a:1,b:(),c:12,d:{}
a=1传入时a就是关键字参数，b,d都未传值，c被传入12，而非默认值。
注意观察参数a, 既可以f(1),也可以f(a=1) 其可读性比第一种更好，建议使用f(a=1)。如果要强制使用f(a=1)，需要在前面添加一个星号:
def f(*,a,**b):print(f'a:{a},b:{b}')
此时f(1)调用，将会报错：TypeError: f() takes 0 positional arguments but 1 was given
只能f(a=1)才能OK.
说明前面的*发挥作用，它变为只能传入关键字参数，那么如何查看这个参数的类型呢？借助python的inspect模块：
In [22]: for name,val in signature(f).parameters.items():
    ...:     print(name,val.kind)
    ...:
a KEYWORD_ONLY
b VAR_KEYWORD
可看到参数a的类型为KEYWORD_ONLY，也就是仅仅为关键字参数。
但是，如果f定义为：
def f(a,*b):print(f'a:{a},b:{b}')
查看参数类型：
In [24]: for name,val in signature(f).parameters.items():
    ...:     print(name,val.kind)
    ...:
a POSITIONAL_OR_KEYWORD
b VAR_POSITIONAL
可以看到参数a既可以是位置参数也可是关键字参数。
27 使用slice对象
生成关于蛋糕的序列cake1：
In [1]: cake1 = list(range(5,0,-1))In [2]: b = cake1[1:10:2]In [3]: bOut[3]: [4, 2]In [4]: cake1Out[4]: [5, 4, 3, 2, 1]
再生成一个序列：
In [5]: from random import randint
   ...: cake2 = [randint(1,100) for _ in range(100)]
   ...: # 同样以间隔为2切前10个元素，得到切片d
   ...: d = cake2[1:10:2]In [6]: dOut[6]: [75, 33, 63, 93, 15]
你看，我们使用同一种切法，分别切开两个蛋糕cake1,cake2. 后来发现这种切法极为经典，又拿它去切更多的容器对象。
那么，为什么不把这种切法封装为一个对象呢？于是就有了slice对象。
定义slice对象极为简单，如把上面的切法定义成slice对象：
perfect_cake_slice_way = slice(1,10,2)#去切cake1
cake1_slice = cake1[perfect_cake_slice_way]
cake2_slice = cake2[perfect_cake_slice_way]In [11]: cake1_sliceOut[11]: [4, 2]In [12]: cake2_sliceOut[12]: [75, 33, 63, 93, 15]
与上面的结果一致。
对于逆向序列切片，slice对象一样可行：
a = [1,3,5,7,9,0,3,5,7]
a_ = a[5:1:-1]
named_slice = slice(5,1,-1)
a_slice = a[named_slice]In [14]: a_Out[14]: [0, 9, 7, 5]In [15]: a_sliceOut[15]: [0, 9, 7, 5]
频繁使用同一切片的操作可使用slice对象抽出来，复用的同时还能提高代码可读性。
28 lambda 函数的动画演示
有些读者反映，lambda函数不太会用，问我能不能解释一下。
比如，下面求这个 lambda函数：
def max_len(*lists):return max(*lists, key=lambda v: len(v))
有两点疑惑：
参数v的取值？
lambda函数有返回值吗？如果有，返回值是多少？
调用上面函数，求出以下三个最长的列表：
r = max_len([1, 2, 3], [4, 5, 6, 7], [8])print(f'更长的列表是{r}')
程序完整运行过程，动画演示如下：
结论：
参数v的可能取值为*lists，也就是 tuple 的一个元素。
lambda函数返回值，等于lambda v冒号后表达式的返回值。
四、 数据结构
29 转为字典　　
创建数据字典
In [1]: dict()Out[1]: {}In [2]: dict(a='a',b='b')Out[2]: {'a': 'a', 'b': 'b'}In [3]: dict(zip(['a','b'],[1,2]))Out[3]: {'a': 1, 'b': 2}In [4]: dict([('a',1),('b',2)])Out[4]: {'a': 1, 'b': 2}
30 冻结集合　　
创建一个不可修改的集合。
In [1]: frozenset([1,1,3,2,3])Out[1]: frozenset({1, 2, 3})
因为不可修改，所以没有像set那样的add和pop方法
31 转为集合类型
返回一个set对象，集合内不允许有重复元素：
In [159]: a = [1,4,2,3,1]In [160]: set(a)Out[160]: {1, 2, 3, 4}
32 转为切片对象
class slice(start, stop[, step])
返回一个表示由 range(start, stop, step) 所指定索引集的 slice对象，它让代码可读性、可维护性变好。
In [1]: a = [1,4,2,3,1]In [2]: my_slice_meaning = slice(0,5,2)In [3]: a[my_slice_meaning]Out[3]: [1, 2, 1]
33 转元组
tuple() 将对象转为一个不可变的序列类型
In [16]: i_am_list = [1,3,5]In [17]: i_am_tuple = tuple(i_am_list)In [18]: i_am_tupleOut[18]: (1, 3, 5)
五、 类和对象
34 是否可调用　　
检查对象是否可被调用
In [1]: callable(str)Out[1]: TrueIn [2]: callable(int)Out[2]: True
In [18]: class Student():
    ...:     def __init__(self,id,name):
    ...:         self.id = id
    ...:         self.name = name
    ...:     def __repr__(self):
    ...:         return 'id = '+self.id +', name = '+self.name
    ...In [19]: xiaoming = Student('001','xiaoming')In [20]: callable(xiaoming)Out[20]: False
如果能调用xiaoming(), 需要重写Student类的__call__方法：
In [1]: class Student():
    ...:     def __init__(self,id,name):
    ...:         self.id = id
    ...:         self.name = name
    ...:     def __repr__(self):
    ...:         return 'id = '+self.id +', name = '+self.name
    ...:     def __call__(self):
    ...:         print('I can be called')
    ...:         print(f'my name is {self.name}')
    ...:In [2]: t = Student('001','xiaoming')In [3]: t()I can be called
my name is xiaoming
35 ascii 展示对象　　
调用对象的 __repr__ 方法，获得该方法的返回值，如下例子返回值为字符串
>>> class Student():def __init__(self,id,name):
        self.id = id
        self.name = namedef __repr__(self):return 'id = '+self.id +', name = '+self.name
调用：
>>> xiaoming = Student(id='1',name='xiaoming')>>> xiaoming
id = 1, name = xiaoming>>> ascii(xiaoming)'id = 1, name = xiaoming'
36 类方法　
classmethod 装饰器对应的函数不需要实例化，不需要 self 参数，但第一个参数需要是表示自身类的 cls 参数，可以来调用类的属性，类的方法，实例化对象等。
In [1]: class Student():
    ...:     def __init__(self,id,name):
    ...:         self.id = id
    ...:         self.name = name
    ...:     def __repr__(self):
    ...:         return 'id = '+self.id +', name = '+self.name
    ...:     @classmethod
    ...:     def f(cls):
    ...:         print(cls)
37 动态删除属性　　
删除对象的属性
In [1]: delattr(xiaoming,'id')In [2]: hasattr(xiaoming,'id')Out[2]: False
38 一键查看对象所有方法　
不带参数时返回当前范围内的变量、方法和定义的类型列表；带参数时返回参数的属性，方法列表。
In [96]: dir(xiaoming)Out[96]:
['__class__','__delattr__','__dict__','__dir__','__doc__','__eq__','__format__','__ge__','__getattribute__','__gt__','__hash__','__init__','__init_subclass__','__le__','__lt__','__module__','__ne__','__new__','__reduce__','__reduce_ex__','__repr__','__setattr__','__sizeof__','__str__','__subclasshook__','__weakref__','name']
39 动态获取对象属性　
获取对象的属性
In [1]: class Student():
   ...:     def __init__(self,id,name):
   ...:         self.id = id
   ...:         self.name = name
   ...:     def __repr__(self):
   ...:         return 'id = '+self.id +', name = '+self.nameIn [2]: xiaoming = Student(id='001',name='xiaoming')In [3]: getattr(xiaoming,'name') # 获取xiaoming这个实例的name属性值Out[3]: 'xiaoming'
40 对象是否有这个属性
In [1]: class Student():
   ...:     def __init__(self,id,name):
   ...:         self.id = id
   ...:         self.name = name
   ...:     def __repr__(self):
   ...:         return 'id = '+self.id +', name = '+self.nameIn [2]: xiaoming = Student(id='001',name='xiaoming')In [3]: hasattr(xiaoming,'name')Out[3]: TrueIn [4]: hasattr(xiaoming,'address')Out[4]: False
41 对象门牌号　
返回对象的内存地址
In [1]: id(xiaoming)Out[1]: 98234208
42 isinstance
判断object是否为类classinfo的实例，是返回true
In [1]: class Student():
   ...:     def __init__(self,id,name):
   ...:         self.id = id
   ...:         self.name = name
   ...:     def __repr__(self):
   ...:         return 'id = '+self.id +', name = '+self.nameIn [2]: xiaoming = Student(id='001',name='xiaoming')In [3]: isinstance(xiaoming,Student)Out[3]: True
43 父子关系鉴定
In [1]: class undergraduate(Student):
    ...:     def studyClass(self):
    ...:         pass
    ...:     def attendActivity(self):
    ...:         passIn [2]: issubclass(undergraduate,Student)Out[2]: TrueIn [3]: issubclass(object,Student)Out[3]: FalseIn [4]: issubclass(Student,object)Out[4]: True
如果class是classinfo元组中某个元素的子类，也会返回True
In [1]: issubclass(int,(int,float))Out[1]: True
44 所有对象之根
object 是所有类的基类
In [1]: o = object()In [2]: type(o)Out[2]: object
45 创建属性的两种方式
返回 property 属性，典型的用法：
class C:def __init__(self):
        self._x = Nonedef getx(self):return self._xdef setx(self, value):
        self._x = valuedef delx(self):del self._x# 使用property类创建 property 属性
    x = property(getx, setx, delx, "I'm the 'x' property.")
使用python装饰器，实现与上完全一样的效果代码：
class C:def __init__(self):
        self._x = None@propertydef x(self):return self._x@x.setterdef x(self, value):
        self._x = value@x.deleterdef x(self):del self._x
46 查看对象类型
class type(name, bases, dict)
传入一个参数时，返回 object 的类型：
In [1]: class Student():
   ...:     def __init__(self,id,name):
   ...:         self.id = id
   ...:         self.name = name
   ...:     def __repr__(self):
   ...:         return 'id = '+self.id +', name = '+self.name
   ...:In [2]: xiaoming = Student(id='001',name='xiaoming')In [3]: type(xiaoming)Out[3]: __main__.StudentIn [4]: type(tuple())Out[4]: tuple
47 元类
xiaoming, xiaohong, xiaozhang 都是学生，这类群体叫做 Student.
Python 定义类的常见方法，使用关键字 class
In [36]: class Student(object):
    ...:     pass
xiaoming, xiaohong, xiaozhang 是类的实例，则：
xiaoming = Student()
xiaohong = Student()
xiaozhang = Student()
创建后，xiaoming 的 __class__ 属性，返回的便是 Student类
In [38]: xiaoming.__class__Out[38]: __main__.Student
问题在于，Student 类有 __class__属性，如果有，返回的又是什么？
In [39]: xiaoming.__class__.__class__Out[39]: type
哇，程序没报错，返回 type
那么，我们不妨猜测：Student 类，类型就是 type
换句话说，Student类就是一个对象，它的类型就是 type
所以，Python 中一切皆对象，类也是对象
Python 中，将描述 Student 类的类被称为：元类。
按照此逻辑延伸，描述元类的类被称为：元元类，开玩笑了~ 描述元类的类也被称为元类。
聪明的朋友会问了，既然 Student 类可创建实例，那么 type 类可创建实例吗？如果能，它创建的实例就叫：类 了。你们真聪明！
说对了，type 类一定能创建实例，比如 Student 类了。
In [40]: Student = type('Student',(),{})In [41]: StudentOut[41]: __main__.Student
它与使用 class 关键字创建的 Student 类一模一样。
Python 的类，因为又是对象，所以和 xiaoming，xiaohong 对象操作相似。支持：
赋值
拷贝
添加属性
作为函数参数
In [43]: StudentMirror = Student # 类直接赋值 # 类直接赋值In [44]: Student.class_property = 'class_property' # 添加类属性In [46]: hasattr(Student, 'class_property')Out[46]: True
元类，确实使用不是那么多，也许先了解这些，就能应付一些场合。就连 Python 界的领袖 Tim Peters 都说：
“元类就是深度的魔法，99%的用户应该根本不必为此操心。
六、工具
48 枚举对象　　
返回一个可以枚举的对象，该对象的next()方法将返回一个元组。
In [1]: s = ["a","b","c"]
    ...: for i ,v in enumerate(s,1):
    ...:     print(i,v)
    ...:1 a2 b3 c
49 查看变量所占字节数
In [1]: import sysIn [2]: a = {'a':1,'b':2.0}In [3]: sys.getsizeof(a) # 占用240个字节Out[3]: 240
50 过滤器　　
在函数中设定过滤条件，迭代元素，保留返回值为True的元素：
In [1]: fil = filter(lambda x: x>10,[1,11,2,45,7,6,13])In [2]: list(fil)Out[2]: [11, 45, 13]
51 返回对象的哈希值　　
返回对象的哈希值，值得注意的是自定义的实例都是可哈希的，list, dict, set等可变对象都是不可哈希的(unhashable)
In [1]: hash(xiaoming)Out[1]: 6139638In [2]: hash([1,2,3])# TypeError: unhashable type: 'list'
52 一键帮助　
返回对象的帮助文档
In [1]: help(xiaoming)Help on Student in module __main__ object:
class Student(builtins.object)|  Methods defined here:||  __init__(self, id, name)||  __repr__(self)||  Data descriptors defined here:||  __dict__|      dictionary for instance variables (if defined)||  __weakref__|      list of weak references to the object (if defined)
53 获取用户输入　
获取用户输入内容
In [1]: input()
aaOut[1]: 'aa'
54 创建迭代器类型
使用iter(obj, sentinel), 返回一个可迭代对象, sentinel可省略(一旦迭代到此元素，立即终止)
In [1]: lst = [1,3,5]In [2]: for i in iter(lst):
    ...:     print(i)
    ...:135
In [1]: class TestIter(object):
    ...:     def __init__(self):
    ...:         self.l=[1,3,2,3,4,5]
    ...:         self.i=iter(self.l)
    ...:     def __call__(self):  #定义了__call__方法的类的实例是可调用的
    ...:         item = next(self.i)
    ...:         print ("__call__ is called,fowhich would return",item)
    ...:         return item
    ...:     def __iter__(self): #支持迭代协议(即定义有__iter__()函数)
    ...:         print ("__iter__ is called!!")
    ...:         return iter(self.l)In [2]: t = TestIter()In [3]: t() # 因为实现了__call__，所以t实例能被调用
__call__ is called,which would return 1Out[3]: 1In [4]: for e in TestIter(): # 因为实现了__iter__方法，所以t能被迭代
    ...:     print(e)
    ...:
__iter__ is called!!132345
55 打开文件
返回文件对象
In [1]: fo = open('D:/a.txt',mode='r', encoding='utf-8')In [2]: fo.read()Out[2]: '\ufefflife is not so long,\nI use Python to play.'
mode取值表：
字符
意义
'r'
读取(默认)
'w'
写入，并先截断文件
'x'
排它性创建，如果文件已存在则失败
'a'
写入，如果文件存在则在末尾追加
'b'
二进制模式
't'
文本模式(默认)
'+'
打开用于更新(读取与写入)
56 创建range序列
range(stop)
range(start, stop[,step])
生成一个不可变序列：
In [1]: range(11)Out[1]: range(0, 11)In [2]: range(0,11,1)Out[2]: range(0, 11)
57 反向迭代器
In [1]: rev = reversed([1,4,2,3,1])In [2]: for i in rev:
     ...:     print(i)
     ...:13241
58 聚合迭代器
创建一个聚合了来自每个可迭代对象中的元素的迭代器：
In [1]: x = [3,2,1]In [2]: y = [4,5,6]In [3]: list(zip(y,x))Out[3]: [(4, 3), (5, 2), (6, 1)]In [4]: a = range(5)In [5]: b = list('abcde')In [6]: bOut[6]: ['a', 'b', 'c', 'd', 'e']In [7]: [str(y) + str(x) for x,y in zip(a,b)]Out[7]: ['a0', 'b1', 'c2', 'd3', 'e4']
59 链式操作
from operator import (add, sub)def add_or_sub(a, b, oper):return (add if oper == '+' else sub)(a, b)add_or_sub(1, 2, '-')  # -1
60 对象序列化
对象序列化，是指将内存中的对象转化为可存储或传输的过程。很多场景，直接一个类对象，传输不方便。
但是，当对象序列化后，就会更加方便，因为约定俗成的，接口间的调用或者发起的 web 请求，一般使用 json 串传输。
实际使用中，一般对类对象序列化。先创建一个 Student 类型，并创建两个实例。
class Student():def __init__(self,**args):
        self.ids = args['ids']
        self.name = args['name']
        self.address = args['address']
xiaoming = Student(ids = 1,name = 'xiaoming',address = '北京')
xiaohong = Student(ids = 2,name = 'xiaohong',address = '南京')
导入 json 模块，调用 dump 方法，就会将列表对象 [xiaoming,xiaohong]，序列化到文件 json.txt 中。
import jsonwith open('json.txt', 'w') as f:
    json.dump([xiaoming,xiaohong], f, default=lambda obj: obj.__dict__, ensure_ascii=False, indent=2, sort_keys=True)
生成的文件内容，如下：
[
    {"address":"北京","ids":1,"name":"xiaoming"
    },
    {"address":"南京","ids":2,"name":"xiaohong"
    }
]