废话

Q：你不是都退役了吗，为什么还更博客？

A：文化课太无聊了，我来更新更新。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Q：不是说不想学多项式了吗，为什么还是学了？

A：下一周有浙大的校赛，然后发现我们队里没有人会多项式，他们都去吃鸡了，于是就(把锅甩给我了)去学了。


多项式乘法

都9102年了还有人不会 \(\text{FFT/NTT}\) 吗，想必任意模数也没啥用，就省略好了。


多项式求逆

只会倍增，假设当前要求
\[ F(x)F'(x)\equiv1(\bmod x^n) \]
并且已知
\[ F(x)F_0'(x)\equiv1(\bmod x^\frac{n}{2}) \]
两式相减可以得到
\[ F(x)(F'(x)-F_0'(x))\equiv0(\bmod x^\frac{n}{2}) \\ F'(x)-F_0'(x)\equiv0(\bmod x^\frac{n}{2}) \\ F'^2(x)-2F'(x)F_0'(x)+F_0'^2(x)\equiv 0(\bmod x^n) \]
乘上 \(F(x)\) 得到
\[ F'(x)-2F_0'(x)+F_0'^2(x)F(x)\equiv0(\bmod x^n) \\ F'(x)\equiv F_0'(x)(2-F_0'(x)F(x)) (\bmod x^n) \]
一次操作需要两次 \(\text{DFT}\) ，复杂度 \(T(n)=T(\frac{n}{2})+\mathcal O(n\log n)=\mathcal O(n\log n)\) 。

code

namespace poly{
    int rev[N], len, lg;
    inline void timesinit(int lenth){
        for(len = 1, lg = 0; len <= lenth; len <<= 1, lg++);
        for(int i = 0; i < len; i++)
            rev[i] = (rev[i>>1] >> 1) | ((i & 1) << (lg - 1));
    }
    inline void DFT(int *a, int sgn){
        for(int i = 0; i < len; i++) if(i < rev[i]) swap(a[i], a[rev[i]]);
        for(int k = 2; k <= len; k <<= 1){
            int w = ~sgn ? Pow(G, (P - 1) / k) : Pow(Pow(G, (P - 1) / k), P - 2);
            for(int i = 0; i < len; i += k){
                int now = 1;
                for(int j = i; j < i + (k >> 1); j++, now = 1ll * now * w % P){
                    int x = a[j], y = 1ll * a[j+(k>>1)] * now % P;
                    a[j] = (x + y) % P, a[j+(k>>1)] = (x - y + P) % P;
                }
            }
        }
        if(sgn == -1){
            int Inv = Pow(len, P - 2);
            for(int i = 0; i < len; i++) a[i] = 1ll * a[i] * Inv % P;
        }
    }
    inline void times(int *a, int *b, int *c){
        for(int i = 0; i < len; i++) c[i] = 1ll * a[i] * b[i] % P;
    }
    inline void getinv(int *a, int *b, int lena){
        if(lena == 1) return (void) (b[0] = Pow(a[0], P - 2));
        getinv(a, b, (lena + 1) / 2);
        static int tmp[N];
        timesinit(lena * 2 - 1);
        for(int i = 0; i < len; i++) tmp[i] = i < lena ? a[i] : 0;
        DFT(tmp, 1), DFT(b, 1);
        for(int i = 0; i < len; i++) 
            b[i] = 1ll * (2 - 1ll * tmp[i] * b[i] % P + P) % P * b[i] % P;
        DFT(b, -1);
        for(int i = lena; i < len; i++) b[i] = 0;
    }
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄