多项式
多项式乘法
FFT，NTT，MTT不是前置知识吗？随便学一下就好了（虽然我到现在还是不会MTT，exlucas也不会用）
FTT总结
NTT总结
泰勒展开
如果一个多项式(f(x))在(x0)时存在n阶导（就是可以求导(n)次），那么可以换成下面这样的一个式子：
(egin{aligned}f(x)&=f(x0)+frac{f^1(x0)}{1!}(x-x0)+frac{f^2(x0)}{2!}(x-x0)^2+...+frac{f^n(x0)}{n!}(x-x0)^n+xi\&=sum_{i=0}^n frac{f^i(x0)}{i!}(x-x0)^i+xiend{aligned})
实在是不想写MathJax了，蒯一波yyb的
反正余项(xi)趋近于无穷小(因为(n)趋近于无穷大),然后就可以忽略了.
然后如果(x0=0)的时候就可以直接搞了。
最常见的就是(e^x),因为这个东西是可以无限求导的.
套到之前的式子里面就是:
(e^x=1+frac{x}{1!}+frac{x^2}{2!}+frac{x^3}{3!}+...)
牛顿迭代
不会证明，背背公式就好了。
(B_{t+1}(x)=B_t(x)-frac{F(B_t(x))}{F'(B_t(x))})
多项式求逆
随便推一下就可以了。
就是考虑(A)为原来的，(B)为逆数组；
这个东西可以套到牛顿迭代的式子里面去，然后就没了。
多项式的其他操作
挖坑待补（一般性都不要用）
生成函数
普通型生成函数(OGF)
给出一个数列(a_0,a_1,a_2,...)
它的OGF就是
指数型生成函数(EGF)
给出一个数列(a_0,a_1,a_2,...)
它的EGF就是
OGF拓展
我们发现如果把斐波那契数列弄成一个生成函数的话,很显然就是:
(F(x)=0+1*x+1*x^2+2*x^3+3*x^4+...)
然后我们同时乘一下(x)
(F'(x)=0+1*x^2+1*x^3+2*x^4+...)
然后裂项一下就是:
(F(x)-F'(x)=0+1*x+0+1*x^3+1*x^4+2*x^5)
然后这样子就变成了:
(x+x^2(0+1*x+1*x^2+...))
也就是说:(F(x)-F'(x)=x+F(x)*x^2)
发现这是一个好东西:
(F(x)-x*F(x)=x+F(x)*x^2)
然后移一下项就是:
(F(x)*(x^2+x-1)*F(x)=-x)
发现我们要求的是(F(x)),就可以写成:
(F(x)=frac{x}{1-x-x^2})
这个东西求的话还是线性的,考虑接着化简
最后就是这么一个烂玩意:
(fib_n = -frac{1}{sqrt5}(frac{1-sqrt5}{2})^n + frac{1}{sqrt5}(frac{1+sqrt5}{2})^n)
OGF和EGF的区别
我们发现EGF的公式多除了一个阶乘,也就意味分子多乘了一个阶乘,那么阶乘在排列组合下的意义是什么?
顺序,所以EGF和OGF的应用也就出来了:
- OGF表示的是组合意义.
- EGF用于求排列下的一些东西
引例:
1.现在有A,B两种物品,A中的物品只能够取奇数个,B中的只能取3的倍数个,求取n个有多少种方法(忽略取出的顺序)
考虑讲这两个写出来就是:
(A(x)=1+3*x+5*x^2+...)
(B(x)=0+3*x+6*x^2+...)
然后把这两个卷起来的第(n)项就是答案
2.现在有A,B两种物品,A中的物品只能够取奇数个,B中的只能取3的倍数个,求取n个有多少种方法(考虑取出的顺序)
考虑顺序的话就是EGF,还是像上面一样写出来
(A(x)=frac{1}{1!}x+frac{1}{3!}x^3+frac{1}{5!}x^5...)
(B(x)=1+frac{1}{2!}x^2+frac{1}{4!}x^4+...)
然后我们就可以感觉这两个东西和我们之前有一个很像:
(e^x=1+frac{x}{1!}+frac{x^2}{2!}+frac{x^3}{3!}+...)
不是吗?
然后考虑(x)与(-x)的展开和这个东西好像截然相反...
然后搞一下就好了.
所以:
(A(x)=frac{e^x-e^{-x}}{2})
(B(x)=frac{e^x+e^{-x}}{2})
然后这两个东西就很简单了.
应用
例题什么的蒯一发yyb的不就好了
字符串配对匹配相关
回文串匹配
考虑下面的这样一个回文串的式子：
(s[x+i]=s[x-i])，显然(x)是回文中心，然后考虑((x-i)+(x+i)=2x)这样的式子，不难发现就是一个卷积，然后就很简单了。
考虑只有两种,a或b,分别对于这两种字母作为1|0搞一下
按照上面的做法卷起来-回文串的个数就是答案了.
有向图计数
具体观看Solution of DAG
未完待续