柒葉灬 的博客

柒葉灬 的博客

生成函数

posted on 2019-10-08 15:33:57 | under 专题总结 |

生成函数


广义二项式定理公式:

$$\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})$

主要递归代码:

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})$

一定要注意:逆元必须开到当前区间长度,并且逆元每次处理前需要清零