多项式板子

技术有限，常数较大，但是方便（

重载了加减乘，写了求逆元、求ln，求exp、求sqrt、求幂(普通)。

#include <vector>
#include <stack>
using namespace std;

namespace polynomial {
    typedef long long ll;
    const int P = 998244353;
    const int g = 3, gi = 332748118;
    int lim, bit;
    vector<int> r;
    struct poly : vector<ll> {
        poly() {};
        poly(ll a)
        {
            resize(1);
            (*this)[0] = (a%P+P)%P;
        }
        poly& modx(int n)
        {
            resize(n);
            return *this;
        }
    };
    inline ll qpow(ll a, ll b, ll p = P)
    {
        ll ans = 1;
        for(; b; b >>= 1, a = a*a%p)
            if(b&1) ans = ans*a%p;
        return ans;
    }
    inline void dnt_prework(int n)
    {
        lim = 1, bit = 0;
        while(lim < n+1) lim <<= 1, bit++;
        r.resize(lim);
        for(int i = 0; i < lim; i++)
            r[i] = (r[i>>1]>>1) | ((i&1)<<(bit-1));
    }
    inline void builtin_change(poly &a, bool type)
    {
        for(int i = 0; i < lim; i++)
            if(i < r[i]) swap(a[i], a[r[i]]);
        for(int mid = 1; mid < lim; mid <<= 1)
        {
            ll wn = qpow(type?g:gi, (P-1)/(mid<<1));
            for(int j = 0, k = 0; j < lim; j += (mid<<1), k = j)
            {
                for(ll w = 1; k < j+mid; k++, w = w*wn%P)
                {
                    ll x = a[k], y = w*a[k+mid]%P;
                    a[k] = (x+y)%P, a[k+mid] = (x-y+P)%P;
                }
            }
        }
    }
    inline void dnt(poly &a)
    {
        a.resize(lim);
        builtin_change(a, true);
    }
    inline void idnt(poly &a)
    {
        a.resize(lim);
        builtin_change(a, false);
        ll liminv = qpow(lim, P-2);
        for(int i = 0; i < lim; i++)
            a[i] = a[i]*liminv%P;
    }
    
    inline poly operator + (const poly &a, const poly &b)
    {
        poly c = a;
        if(a.size() < b.size()) c.resize(b.size());
        for(int i = 0; i < b.size(); i++)
            c[i] = (c[i]+b[i])%P;
        return c;
    }
    inline poly operator - (const poly &a, const poly &b)
    {
        poly c = a;
        if(a.size() < b.size()) c.resize(b.size());
        for(int i = 0; i < b.size(); i++)
            c[i] = (c[i]-b[i]+P)%P;
        return c;
    }
    poly operator * (poly a, poly b)
    {
        int len = a.size()+b.size()-2;
        dnt_prework(len);
        poly ans; ans.resize(lim+1);
        dnt(a); dnt(b);
        for(int i = 0; i < lim; i++)
            ans[i] = a[i]*b[i]%P;
        idnt(ans);
        ans.resize(len+1);
        return ans;
    }
    inline poly operator * (poly a, const ll &k)
    {
        for(int i = 0; i < a.size(); i++)
            a[i] = a[i]*k%P;
        return a;
    }
    
    inline poly derivation(const poly &a)
    {
        poly b; b.resize(a.size()-1);
        for(int i = 1; i < a.size(); i++)
            b[i-1] = a[i]*i%P;
        return b;
    }
    inline poly integral(const poly &a)
    {
        poly b; b.resize(a.size()+1);
        for(int i = a.size()-1; i >= 1; i--)
            b[i] = a[i-1]*qpow(i, P-2)%P;
        return b;
    }
    inline poly inv(const poly &a)
    {
        stack<int> st;
        int n = a.size();
        while(n > 1) st.push(n), n = (n+1)/2;
        poly b = qpow(a[0], P-2);
        while(st.size())
        {
            n = st.top(); st.pop();
            poly c = a; c.modx(n); b.modx(n);
            b = (b*2-((c*b).modx(n)*b).modx(n)).modx(n);
        }
        return b.modx(a.size());
    }
    inline poly ln(const poly &a)
    {
        poly b, tmp;
        b = integral((derivation(a)*inv(a)));
        return b.modx(a.size());
    }
    inline poly sqrt(const poly &a)
    {
        stack<int> st;
        int n = a.size();
        while(n > 1) st.push(n), n = (n+1)/2;
        poly b = qpow(a[0], P-2);
        while(st.size())
        {
            n = st.top(); st.pop();
            poly c = a;
            c.modx(n); b.modx(n);
            b = ((c+(b*b).modx(n))*inv(b*2)).modx(n);
        }
        return b.modx(a.size());
    }
    inline poly exp(const poly &a)
    {
        stack<int> st;
        int n = a.size();
        while(n > 1) st.push(n), n = (n+1)/2;
        poly b = 1;
        while(st.size())
        {
            n = st.top(); st.pop();
            poly c = a;
            b.modx(n); c.modx(n);
            b = ((1-ln(b)+c)*b).modx(n);
        }
        return b.modx(a.size());
    }
    inline poly pow(const poly &a, const ll &k)
    {
        return exp(k*ln(a));
    }
}
using namespace polynomial;