前置知识：
一，导数
倒数其实就是函数的斜率函数
设D[f(x)]表示f(x)的导数，则满足
$$1，D[f(x)]=\lim\limits_{\delta x->\infty}\frac{f(x+\delta x)-f(x)}{\delta x}$$
$$2,f(x+\delta x)=f(x)+D[f(x)]\times \delta x$$
I，常用导数
有$$e=\lim\limits_{x->0}(1+\frac{1}{n})^{n}$$
II，泰勒展开
$$f(x)=\sum\limits_{i=0}^{n}\frac{f^{(0)}(x_{0})(x-x_{0})^{i}}{i!}$$
III,级数求和
1,$$e^{x}=\sum\limits_{n->+\infty}\frac{x^{i}}{i!}$$
2,$$\frac{1}{1-x}=\lim\limits_{n->+\infty}\sum_{i=0}^{n}x^{i}$$
3,$$\frac{1}{1+x}=\lim\limits_{n->+\infty}\sum_{i=0}^{n}(-1)^{i}x^{i}$$
4,$$sin(x)=\lim\limits_{n->+\infty}\sum_{i=1}^{n}(-1)^{i-1}\frac{x^{2i-1}}{(2i-1)!}$$
5,$$cos(x)=\lim\limits_{n->+\infty}\sum_{i=0}^{n}(-1)^{i}\frac{x^{2i}}{(2i)!}$$
6,$$ln(x+1)=\lim\limits_{n->+\infty}\sum_{i=1}^{n}(-1)^{i-1}\frac{x^{i}}{i}$$
先放个fft和ntt的板子
1 const double pi=acos(-1);
2 struct cplx{
3 double rl,ig;
4 cplx(double r=0,double i=0){
5 this->rl=r;
6 this->ig=i;
7 }
8 friend cplx operator + (const cplx &a,const cplx &b){
9 return cplx(a.rl+b.rl,a.ig+b.ig);
10 }
11 friend cplx operator - (const cplx &a,const cplx &b){
12 return cplx(a.rl-b.rl,a.ig-b.ig);
13 }
14 friend cplx operator * (const cplx &a,const cplx &b){
15 return cplx(a.rl*b.rl-a.ig*b.ig,a.rl*b.ig+b.rl*a.ig);
16 }
17 }a[300010],b[300010],c[300010];
18 int n,m,bin=1,bct,len,v[300010];
19 inline void fft(cplx *now,int l,int opt){
20 for(int i=0;i<l;i++)
21 if(i<v[i]) swap(now[i],now[v[i]]);
22 for(int i=1;i<l;i<<=1){
23 cplx wn=cplx(cos(pi/i),opt*sin(pi/i));
24 for(int j=0;j<l;j+=(i<<1)){
25 cplx w=cplx(1,0);
26 for(int k=0;k<i;k++,w=w*wn){
27 cplx x=now[j+k];
28 cplx y=w*now[j+k+i];
29 now[j+k]=x+y;
30 now[j+k+i]=x-y;
31 }
32 }
33 }
34 } 1 inline int qpow(int a,int b,int ans=1){
2 for(;b;b>>=1,a=1ll*a*a%mod)
3 if(b&1) ans=1ll*ans*a%mod;
4 return ans;
5 }
6 inline void fft(int *now,int l,int opt){
7 for(int i=0;i<l;i++)
8 if(i<v[i]) swap(now[i],now[v[i]]);
9 for(int i=1;i<l;i<<=1){
10 ll wn=qpow(3,((opt*(mod-1))/(i<<1)+mod-1)%(mod-1));
11 for(int j=0;j<l;j+=(i<<1)){
12 ll w=1;
13 for(int k=0;k<i;k++,w=w*wn%mod){
14 int x=now[j+k],y=w*now[j+k+i]%mod;
15 now[j+k]=(x+y)%mod;
16 now[j+k+i]=(x-y+mod)%mod;;
17 }
18 }
19 }
20 }通常用来解决卷积形式的快速求解，即在$O(nlogn)$的复杂度内求解$F_{i}=\sum\limits_{j=0}^{i}A_{j}\times B_{i-j}$
一般要和化柿子结合
放几道例题
化一下柿子
$$f(n)=\sum\limits_{i=0}^{n} \sum\limits_{j=0}^{i} 2^j \times \sum\limits_{k=0}^{j} (-1)^k \times \frac{j!}{k! \times (j-k)!} \times (j-k)^i$$
$$=\sum\limits_{i=0}^{n} \sum\limits_{j=0}^{i} 2^j \times j! \times \sum\limits_{k=0}^{j} \frac{(j-k)^i}{(j-k)!} \times \frac{(-1)^k}{k!}$$
$$=\sum\limits_{j=0}^{n} 2^j \times j! \times \sum\limits_{k=0}^{j} \frac{\sum\limits_{i=0}^{n}(j-k)^i}{(j-k)!} \times \frac{(-1)^k}{k!}$$
设$g(x)=\sum\limits_{i=0}^{n}(j-k)^{i}$这是个等比数列求和，可以$O(1)$得到
则$$=\sum\limits_{j=0}^{n} 2^j \times j! \times \sum\limits_{k=0}^{j} \frac{g(x)}{(j-k)!} \times \frac{(-1)^k}{k!}$$
满足卷积形式，可以ntt了