生成函数

# 生成函数 ---- 广义二项式定理公式： $$\displaystyle (a+b)^α=\sum_{k=0}^{\infty} \frac{α(α-1) \dots (α-k+1)}{k!} x^{α-k}y^{k} $$ ### 多项式求逆 求$A(x)B(x) \equiv 1 (mod \ x^n)$ 只要记住$ B(x)=2B'(x)-A(x)B'^2(x)$ 就行了 $A(x)B'(x) \equiv 1 (mod \ \frac{n}{2})$ 主要递归代码： ```cpp long long tmp[maxn]; void solve(int n){ if(n==1){ B[0]=qpow(A[0],P-2); return; } solve(n>>1); calc(tmp,B,B,(n>>1)-1); calc(tmp,tmp,A,n-1); for(int i=0;i<n;i++){ B[i]=(2*B[i]-tmp[i]+P)%P; } } ``` -------- ### 多项式开根 求$B^2(x) \equiv A(x) (mod \ x^n)$ 只要记住$ B(x)={A(x)+B'^2(x) \over 2B'(x)}=\frac{A(x)}{2B'(x)}+\frac{B'(x)}{2}=\frac{1}{2}(\frac{A(x)}{B'(x)}+B'(x))$ 就行了 $B'^2(x) \equiv A(x) (mod \ \frac{n}{2})$ 一定要注意：逆元必须开到当前区间长度，并且逆元每次处理前需要清零