概率期望
咕咕咕(?)
基础知识都在课件上不想手打了,好像都挺简单的
再谈生成函数
最近仔细研究了一下/hanx,发现自己以前理解的有些问题
广义二项式定理
\((1+x)^a=\sum_{n\ge 0}(a,n)x^n[a:R]\)
广义二项式系数
\((n,m)=\frac{n(n-1)...(n-m+1)}{m!}\)
对于一个数列{\(f_n\)}
OGF:\(F(x)=\sum_{n\ge 0}f_nx^n\)
EGF:\(F(x)=\sum_{n\ge 0}f_n\frac{x^n}{n!}\)
常见生成函数及运算
OGF:
满足数乘,卷积,加法
\((\sum_{n\ge 0}f_nx^n)\times(\sum_{n\ge 0}g_nx^n)=\sum_{n\ge 0}(\sum_{i=0}^nf_ig_{n-i})x^n\)
EGF:
满足数乘,卷积,加法
\((\sum_{n\ge 0}f_n\frac{x^n}{n!})\times(\sum_{n\ge 0}g_n\frac{x^n}{n!})=\sum_{n\ge 0}(\sum_{i=0}^n(n,i)f_ig_{n-i})\frac{x^n}{n!}\)
其实一些简单的完全可以现退,这里就放出一些基本不会推出来的
\(\sum_{n\ge 0}x^n=\frac{1}{1-x}\)
\(\sum_{n\ge m}x^n=\frac{x^m}{1-x}\)
\(\sum_{n\ge 0}a^nx^n=\frac{1}{1-ax}\)
\(\sum_{n\ge 0}(n+k-1,n)x^n=\frac{1}{(1-x)^k}\)
\(\sum_{n\ge 0}\frac{c^nx^n}{n!}=e^{cx}\)
斐波那契
\(F(x)=\frac{x}{1-x-x^2}\),再因式分解一下
卡特兰数
用最朴素的递推公式,发现是个卷积的形式,展开带入得
\(F(x)=1+xF^2(x)\),解得
\(F(x)=\frac{1-\sqrt{1-4x}}{2x}\)
再用广义二项式定理展开回带即可得出
\(f_n=\frac{(2n,n)}{n+1}\)
指数型生成函数
牵扯到好多微积分的知识,但我只会求导啊/lllll
一些常见的EGF:(直接泰勒展开!)
\(\sum_{n\ge 0}\frac{x^n}{n!}=e^x~~[~1,1,1...~]~\)
\(\sum_{n\ge 0}(-1)^n~\frac{x^n}{n!}=e^{-x}~~[~1,-1,1...~]~\)
\(\sum_{n\ge 0}c^n\frac{x^n}{n!}=e^{cx}~~[~1,c,c^2,c^3...~]\)
\(\sum_{n\ge 1}(n-1)!\frac{x^n}{n!}=ln~\frac{1}{1-x}~~[~0!,1!,2!,...~]\)
移位
求导左移,积分右移
所有常见生成函数
有点乱,见
https://rqy.moe/Algorithms/generating-function/
贝尔数--exp
不容易啊不容易啊
将n个有区别的小球放进任意多个无区别的箱子的方案数,即将一个大小为n的集合划分成若干个不相交非空子集的并的方案数,有递推式(当然你可以斯特灵数)
\(w_{n+1}=\sum_{i=0}^n(n,i)w_{n-i}+[n=0]\)
相当于{\(1\)}和{\(w_n\)}的二项卷积
\(W(x)=∫W(x)e^x+1\)
求导得
\(\frac{W(x)'}{W(x)}=e^x\)
积分得
\(ln~W(x)=e^x+C\)
于是
\(W(x)=e^{e^x-1}=\exp(e^x-1)\)
这可以扩展到一类图计数问题
多项式
期待好久了....
复数单位根
\(x^n=1\)
\(w_n^k=\cos \frac{2\pi k}{n}+\sin \frac{2\pi k}{n}i\)
\(w_{dn}^{dk}=w_n^k\)
\(w_n^{k+n}=w_n^k\)
\(w_n^{k+\frac{n}{2}}=-w_n^k\)
\((w_n^k)^d=w_n^{kd}\)
\(w_n^0=w_n^n=1\)
FFT
算两个多项式的乘积,通过ianzhi
对于一个多项式A(x)=\(\sum_{i=0}^{n-1}a_ix^i\),假设\(n=2^k\)
我们可以得出递归式子
点值表示法:我们可以将0-n-1的\(w_n^i\)为根带进去
共有3步
1.将多项式化为DFT
2.\(DFT(f*g)=DFT(f)*DFT(g)\) \((x_1,f(x_1)g(x_1))\)
3.将DFT变回一个多项式
\(A_0(x)=a_0+a_2x+a_4x^2+....a_{n-2}x^{\frac{n}{2}-1}\)
\(A_1(x)=a_1+a_3x+a_5x^2+....a_{n-1}x^{\frac{n}{2}-1}\)
\(A(x)=A_0(x^2)+xA_1(x^2)\)
\(A(w_n^k)=A_0(w_{\frac{n}{2}}^{k})+w_n^kA_1(w_{\frac{n}{2}}^{k})\)
但是复杂度是个n^2的...
\(A(w_n^{k+\frac{n}{2}})=A_0(w_{\frac{n}{2}}^{k})-w_n^kA_1(w_{\frac{n}{2}}^{k})\)
n个n次多项式->n个n/2次多项式->n个n/4次的多项式->...->n个1次多项式
复杂度O(nlogn)
但是操作3怎办?
IDFT
我们已知\((w_n^0,f(w_n^0))....\)若干个多项式乘积后的DFT,考虑重新定义多项式
\(Y(x)=\sum_{i=0}^nf(w_n^i)x^i\)
拆开整理一下
在定义Y的点值\((w_n^{-k},c_k)\)
整理得\(c_k=a_kn\)
于是求一下\(c_k\)的值就行了
NTT
求出一个原根,发现单位根的性质都满足,于是随便做了
998244353=119*2^23+1 原根为3
FWT
巨坑,待填,暂且放着
多项式求逆
求\(~A(x)B(x)\equiv1~(mod~~ x^n)\)
n=1时就是个逆元
于是我们可以递归求解,n->n/2上取整
得到
\(B(x)\equiv2C(x)-A(x)C(x)^2~(mod~~x^n)\)
用ntt加速即可
多项式开根
求 \(~B(x)^2\equiv A(x)~(mod~~x^n)\)
\(B(x)\equiv\frac{C(x)^2+A(x)}{2C(x)}~(mod~~x^n)\)
多项式除法
注意:这不是在取模意义下!
给定\(~A(x)~B(x)~\)要求求出一对\(~C(x)~D(x)~\)
使得\(~A(x)=B(x)C(x)+D(x)~\)且最高次项分别为n m n-m <m
考虑定义一个新的函数\(rev(F(x))=x^nF(\frac{1}{x})\)
则
\(rev(A(x))\equiv rev(B(x))rev(C(x))~(mod~~x^{n-m+1})\)
然后多项式求逆就完了
多项式取对数
求\(~g(x)\equiv ln~f(x)~(mod~~x^n)~\)
求导,求逆,积分,得
\(~g'(x)\equiv \frac{f'(x)}{f(x)}(mod~~x^n)~\)
多项式exp
求\(g(x)\equiv e^{f(x)}~(mod~~x^n)\)
取log得
\(ln~g(x)\equiv f(x)~(mod~~x^n)\)
定义多项式函数\(h(g(x))=ln~g(x)-f(x)\)
即求这个函数的零点,求导得
\(h'(g(x))=\frac{1}{g(x)}\)
现在考虑我们求得
\(h(g_0(x))\equiv 0~(mod~~x^n)~=>~h(g_1(x))\equiv 0~(mod~~x^{2n})\)
有
\(g_1(x)-g_0(x)\equiv 0~(mod~~x^n)\)
\(h(g_1(x))\equiv h(g_0(x))+h'(g_0(x))(g_1(x)-g_0(x))\equiv 0~(mod~~x^{2n})\)
即
\(g_1(x)\equiv g_0(x)+g_0(x)(f(x)-ln~g_0(x))~(mod~~x^{2n})\)
泰勒展开
对于任意一个函数\(~f(x)~\)她的泰勒展开为
\(~f(x)=\frac{f(x_0)}{0!}+\frac{f^{(1)}(x_0)}{1!}(x-x_0)+\frac{f^{(2)}(x_0)}{2!}(x-x_0)^2+..........~\)
多项式快速幂
求\(~f(x)^k~mod~~x^n~\)
当然可以倍增做
可以写成\(~f(x)^k=e^{k~lnf(x)}~\)
\((a^b=e^{b~ln~a})\)