多项式模板

using namespace std;

namespace Polynomial {

typedef long long LL;

const int K = 21, N = 1 << K;
const LL MOD = 998244353;

LL Pow(LL a, LL b) {
    LL c = 1;
    for (; b; a = a * a % MOD, b >>= 1)
        if (b & 1) c = c * a % MOD;
    return c;
}

LL inv[N];

void InitInv() {
    inv[1] = 1;
    for (int i = 2; i < N; ++i)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    return;
}

void Init(int k, int *sp, LL *w) {
    int n = 1 << k;
    w[0] = 1;
    w[1] = Pow(3, (MOD - 1) / n);
    for (int i = 2; i < n; ++i)
        w[i] = w[i - 1] * w[1] % MOD;
    sp[0] = 0;
    for (int i = 1; i < n; ++i)
        sp[i] = (sp[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
    return;
}

void DFT(vector &a, int k) {
    static int _k = 0;
    static int _sp[N * 2], *sp[K];
    static LL _w[N * 2], *w[K];
    for (; _k < k; ) {
        ++_k;
        sp[_k] = _sp + (1 << _k) - 1;
        w[_k] = _w + (1 << _k) - 1;
        Init(_k, sp[_k], w[_k]);
    }
    int n = 1 << k;
    for (int i = 0; i < n; ++i)
        if (i < sp[k][i]) swap(a[i], a[sp[k][i]]);
    for (int j = 1; j <= k; ++j) {
        int l = 1 << j, m = l >> 1;
        for (vector :: iterator p = a.begin(); p != a.end(); p += l)
            for (int i = 0; i < m; ++i) {
                LL t = p[i + m] * w[j][i] % MOD;
                if ((p[i + m] = p[i] - t) < 0) p[i + m] += MOD;
                if ((p[i] += t) >= MOD) p[i] -= MOD;
            }
    }
    return;
}

void IDFT(vector &a, int k) {
    DFT(a, k);
    int n = 1 << k, inv = Pow(n, MOD - 2);
    reverse(a.begin() + 1, a.end());
    for (int i = 0; i < n; ++i)
        (a[i] *= inv) %= MOD;
    return;
}

vector Multiply(vector a, vector b) {
    int _n = a.size(), _m = b.size(), k, n;
    for (k = 1; (1 << k) < (_n + _m - 1); ++k);
    n = 1 << k;
    a.resize(n);
    b.resize(n);
    DFT(a, k);
    DFT(b, k);
    for (int i = 0; i < n; ++i)
        (a[i] *= b[i]) %= MOD;
    IDFT(a, k);
    a.resize(_n + _m - 1);
    return a;
}
vector Multiply(vector a, vector b, int m) {
    if ((int)a.size() > m) a.resize(m);
    if ((int)b.size() > m) b.resize(m);
    int _n = a.size(), _m = b.size(), k, n;
    for (k = 1; (1 << k) < (_n + _m - 1); ++k);
    n = 1 << k;
    a.resize(n);
    b.resize(n);
    DFT(a, k);
    DFT(b, k);
    for (int i = 0; i < n; ++i)
        (a[i] *= b[i]) %= MOD;
    IDFT(a, k);
    a.resize(m);
    return a;
}
vector* _Multiply(vector &a, vector b) {
    int _n = a.size(), _m = b.size(), k, n;
    for (k = 1; (1 << k) < (_n + _m - 1); ++k);
    n = 1 << k;
    a.resize(n);
    b.resize(n);
    DFT(a, k);
    DFT(b, k);
    for (int i = 0; i < n; ++i)
        (a[i] *= b[i]) %= MOD;
    IDFT(a, k);
    a.resize(_n + _m - 1);
    return &a;
}
vector* _Multiply(vector &a, vector b, int m) {
    if ((int)b.size() > m) b.resize(m);
    int _n = a.size(), _m = b.size(), k, n;
    for (k = 1; (1 << k) < (_n + _m - 1); ++k);
    n = 1 << k;
    a.resize(n);
    b.resize(n);
    DFT(a, k);
    DFT(b, k);
    for (int i = 0; i < n; ++i)
        (a[i] *= b[i]) %= MOD;
    IDFT(a, k);
    a.resize(m);
    return &a;
}

vector Multiply(vector a, LL b) {
    b %= MOD;
    int n = a.size();
    for (int i = 0; i < n; ++i)
        a[i] = a[i] * b % MOD;
    return a;
}
vector* _Multiply(vector &a, LL b) {
    b %= MOD;
    int n = a.size();
    for (int i = 0; i < n; ++i)
        a[i] = a[i] * b % MOD;
    return &a;
}
 
vector Resize(vector a, int n) {
    return a.resize(n), a;
}
vector* _Resize(vector &a, int n) {
    a.resize(n);
    return &a;
}
 
vector Reciprocal(const vector &a) {
    int _n = a.size();
    if (!a[0]) {
        cerr << "irreversible" << endl;
        throw;
    }
    vector b(1, Pow(a[0], MOD - 2)), c;
    for (int n = 1, k = 0; n < _n; ) {
        n <<= 1;
        ++k;
        b.resize(n * 2);
        c.resize(n * 2);
        for (int i = 0; i < n; ++i)
            c[i] = (i < _n) ? a[i] : 0;
        DFT(b, k + 1);
        DFT(c, k + 1);
        for (int i = 0; i < n * 2; ++i)
            b[i] = b[i] * (MOD + 2 - b[i] * c[i] % MOD) % MOD;
        IDFT(b, k + 1);
        fill(b.begin() + n, b.end(), 0);
    }
    b.resize(_n);
    return b;
}

vector LeftShift(vector a, int n) {
    int _n = a.size();
    a.resize(_n + n);
    for (int i = _n + n - 1; i >= n; --i)
        a[i] = a[i - n];
    for (int i = 0; i < n; ++i)
        a[i] = 0;
    return a;
}
vector* _LeftShift(vector &a, int n) {
    int _n = a.size();
    a.resize(_n + n);
    for (int i = _n + n - 1; i >= n; --i)
        a[i] = a[i - n];
    for (int i = 0; i < n; ++i)
        a[i] = 0;
    return &a;
}
 
vector RightShift(vector a, int n) {
    int _n = a.size();
    for (int i = 0; i + n < _n; ++i)
        a[i] = a[i + n];
    if (_n - n > 0) a.resize(_n - n);
    else a = vector(1);
    return a;
}
vector* _RightShift(vector &a, int n) {
    int _n = a.size();
    for (int i = 0; i + n < _n; ++i)
        a[i] = a[i + n];
    if (_n - n > 0) a.resize(_n - n);
    else a = vector(1);
    return &a;
}
 
vector Add(vector a, const vector &b) {
    if (a.size() < b.size()) a.resize(b.size());
    for (int i = 0; i < (int)b.size(); ++i)
        if ((a[i] += b[i]) >= MOD) a[i] -= MOD;
    return a;
}
vector* _Add(vector &a, const vector &b) {
    if (a.size() < b.size()) a.resize(b.size());
    for (int i = 0; i < (int)b.size(); ++i)
        if ((a[i] += b[i]) >= MOD) a[i] -= MOD;
    return &a;
}

vector Add(vector a, LL b) {
    a[0] = (a[0] + b) % MOD;
    return a;
}
vector* _Add(vector &a, LL b) {
    a[0] = (a[0] + b) % MOD;
    return &a;
}
 
vector Subtract(vector a, const vector &b) {
    if (a.size() < b.size()) a.resize(b.size());
    for (int i = 0; i < (int)b.size(); ++i)
        if ((a[i] -= b[i]) < 0) a[i] += MOD;
    return a;
}
vector* _Subtract(vector &a, const vector &b) {
    if (a.size() < b.size()) a.resize(b.size());
    for (int i = 0; i < (int)b.size(); ++i)
        if ((a[i] -= b[i]) < 0) a[i] += MOD;
    return &a;
}
 
vector Subtract(vector a, LL b) {
    a[0] = (a[0] + MOD - b) % MOD;
    return a;
}
vector* _Subtract(vector &a, LL b) {
    a[0] = (a[0] + MOD - b) % MOD;
    return &a;
}
 
vector Divide(vector a, LL b) {
    LL inv = Pow(b % MOD, MOD - 2);
    int n = a.size();
    for (int i = 0; i < n; ++i)
        a[i] = a[i] * inv % MOD;
    return a;
}
vector* _Divide(vector &a, LL b) {
    LL inv = Pow(b % MOD, MOD - 2);
    int n = a.size();
    for (int i = 0; i < n; ++i)
        a[i] = a[i] * inv % MOD;
    return &a;
}
 
vector Divide(vector a, vector b) {
    int n = (int)a.size() - 1, m = (int)b.size() - 1;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    a.resize(n - m + 1);
    b.resize(n - m + 1);
    a = Multiply(a, Reciprocal(b), n - m + 1);
    reverse(a.begin(), a.end());
    return a;
}
 
vector Modulo(const vector &a, const vector &b) {
    int m = (int)b.size() - 1;
    return Resize(Subtract(a, Multiply(Divide(a, b), b)), m);
}
 
vector Derivative(vector a) {
    int n = a.size();
    for (int i = 0; i + 1 < n; ++i)
        a[i] = a[i + 1] * (i + 1) % MOD;
    if (n > 1) a.resize(n - 1);
    return a;
}
vector* _Derivative(vector &a) {
    int n = a.size();
    for (int i = 0; i + 1 < n; ++i)
        a[i] = a[i + 1] * (i + 1) % MOD;
    if (n > 1) a.resize(n - 1);
    return &a;
}

vector Integral(vector a) {
    int n = a.size();
    a.resize(n + 1);
    for (int i = n; i; --i)
        a[i] = a[i - 1] * inv[i] % MOD;
    a[0] = 0;
    return a;
}
vector* _Integral(vector &a) {
    int n = a.size();
    a.resize(n + 1);
    for (int i = n; i; --i)
        a[i] = a[i - 1] * inv[i] % MOD;
    a[0] = 0;
    return &a;
}
 
vector Logarithm(vector a) {
    if (a[0] != 1) {
        cerr << "logarithm function undefined" << endl;
        throw;
    }
    int n = a.size();
    return Integral(Multiply(Derivative(a), Reciprocal(a), n - 1));
}
vector* _Logarithm(vector &a) {
    if (a[0] != 1) {
        cerr << "logarithm function undefined" << endl;
        throw;
    }
    int n = a.size();
    return _Integral(*_Multiply(*_Derivative(a), Reciprocal(a), n - 1));
}

vector Exponential(vector a) {
    if (a[0]) {
        cerr << "exponential function undefined" << endl;
        throw;
    }
    int _n = a.size();
    vector b(1, 1);
    for (int n = 1; n < _n; ) {
        n <<= 1;
        b.resize(n);
        _Multiply(b, Add(Subtract(vector(1, 1), Logarithm(b)), Resize(a, n)), n);
    }
    return *_Resize(b, _n);
}
 
vector Pow(vector a, LL b) {
    int n = a.size(), k;
    for (k = 0; k < n && !a[k]; ++k);
    LL c = a[k];
    _RightShift(a, k);
    _Divide(a, c);
    a.resize(n);
    a = Exponential(*_Multiply(*_Logarithm(a), b));
    _Multiply(a, Pow(c, b));
    if (k * b >= n) return vector(n, 0);
    return *_Resize(*_LeftShift(a, k * b), n);
}
     
struct Poly {
    vector c;
     
    Poly(vector c = vector(1)) : c(c) {}
     
    Poly(LL x) {
        c.resize(1);
        c[0] = x;
        return;
    }

    Poly* operator = (const LL x) {
        c.resize(1);
        c[0] = x;
        return this;
    }

    Poly Reciprocal() {
        return Poly(Polynomial::Reciprocal(c));
    }

    Poly Logarithm() {
        return Poly(Polynomial::Logarithm(c));
    }
     
    Poly* _Logarithm() {
        Polynomial::_Logarithm(c);
        return this;
    }

    Poly Exponential() {
        return Poly(Polynomial::Exponential(c));
    }

    Poly Pow(LL b) {
        return Poly(Polynomial::Pow(c, b));
    }

    Poly* Resize(int n) {
        c.resize(n);
        return this;
    }
     
    void _Resize(int n) {
        c.resize(n);
        return;
    }
     
    inline int Deg() const {
        return (int)c.size() - 1;
    }
     
    void Clear() {
        c = vector(1);
        return;
    }

    void Read(int n) {
        c.clear();
        c.resize(n + 1);
        for (int i = 0; i <= n; ++i) {
            scanf("%lld", &c[i]);
            c[i] %= MOD;
        }
        return;
    }

    void Print() {
        for (LL x : c)
            printf("%lld ", x);
        puts("");
        return;
    }
     
};

Poly Read(int n) {
    Poly a;
    a.Read(n);
    return a;
}
 
void _Read(int n, Poly &a) {
    a.Read(n);
    return;
}

void Print(Poly a) {
    a.Print();
    return;
}
 
void _Print(Poly &a) {
    a.Print();
    return;
}

Poly Resize(Poly a, int n) {
    return *a.Resize(n);
}

Poly* _Resize(Poly &a, int n) {
    a._Resize(n);
    return &a;
}

Poly Reciprocal(Poly &a) {
    return a.Reciprocal();
}

Poly Logarithm(Poly &a) {
    return a.Logarithm();
}

Poly* _Logarithm(Poly &a) {
    return a._Logarithm();
}

Poly Exponential(Poly &a) {
    return a.Exponential();
}

Poly Pow(Poly &a, LL b) {
    return a.Pow(b);
}

Poly operator << (const Poly &a, int n) {
    return Poly(LeftShift(a.c, n));
}

Poly* operator <<= (Poly &a, int n) {
    _LeftShift(a.c, n);
    return &a;
}
 
Poly operator >> (const Poly &a, int n) {
    return Poly(RightShift(a.c, n));
}

Poly* operator >>= (Poly &a, int n) {
    _RightShift(a.c, n);
    return &a;
}
 
Poly operator + (const Poly &a, const Poly &b) {
    return Poly(Add(a.c, b.c));
}

Poly operator + (const Poly &a, LL b) {
    return Poly(Add(a.c, b));
}
 
Poly* operator += (Poly &a, const Poly &b) {
    _Add(a.c, b.c);
    return &a;
}
 
Poly* operator += (Poly &a, LL b) {
    _Add(a.c, b);
    return &a;
}
 
Poly operator - (const Poly &a, const Poly &b) {
    return Poly(Subtract(a.c, b.c));
}
 
Poly operator - (const Poly &a, LL b) {
    return Poly(Subtract(a.c, b));
}
 
Poly* operator -= (Poly &a, const Poly &b) {
    _Subtract(a.c, b.c);
    return &a;
}
 
Poly* operator -= (Poly &a, LL b) {
    _Subtract(a.c, b);
    return &a;
}
 
Poly operator * (const Poly &a, const Poly &b) {
    return Poly(Multiply(a.c, b.c));
}
 
Poly operator * (const Poly &a, LL b) {
    return Poly(Multiply(a.c, b));
}
 
Poly* operator *= (Poly &a, LL b) {
    _Multiply(a.c, b);
    return &a;
}
 
Poly* operator *= (Poly &a, const Poly &b) {
    _Multiply(a.c, b.c);
    return &a;
}

Poly operator / (const Poly &a, const Poly &b) {
    return Poly(Divide(a.c, b.c));
}
 
Poly operator / (const Poly &a, LL b) {
    return Poly(Divide(a.c, b));
}
 
Poly* operator /= (Poly &a, const Poly &b) {
    a.c = Divide(a.c, b.c);
    return &a;
}
 
Poly* operator /= (Poly &a, LL b) {
    _Divide(a.c, b);
    return &a;
}
 
Poly operator % (const Poly &a, const Poly &b) {
    return Poly(Modulo(a.c, b.c));
}

Poly* operator %= (Poly &a, const Poly &b) {
    a.c = Modulo(a.c, b.c);
    return &a;
}

using namespace Polynomial;

Poly a, b;

int main() {
InitInv();
int n;
LL k;
scanf("%d%lld", &n, &k);
_Read(n - 1, a);
Print(Pow(a, k));
return 0;
}

模板4 多点求值 int版
[luogu5050 【模板】多项式多点求值](https://www.luogu.org/problemnew/show/P5050)
```cpp
#include 

using namespace std;

typedef long long LL;

const int MOD = 998244353;

inline int Add(int a, int b) {
    return (a + b >= MOD) ? (a + b - MOD) : (a + b);
}
inline int Sub(int a, int b) {
    return (a >= b) ? (a - b) : (a - b + MOD);
}
inline int Mul(int a, int b) {
    return (LL)a * b % MOD;
}
inline int Pow(int a, int b) {
    int c = 1;
    for (; b; a = Mul(a, a), b >>= 1)
        if (b & 1) c = Mul(c, a);
    return c;
}


namespace Poly {

    const int K = 22, N = 1 << K;

    // int inv[N];

    // void InitINV() {
    //     inv[1] = 1;
    //     for (int i = 2; i < N; ++i)
    //         inv[i] = Mul(Sub(0, MOD / i), inv[MOD % i]);
    //     return;
    // }
    
    void Init(int k, int *rev, int *w) {
        int n = 1 << k;
        rev[0] = 0;
        for (int i = 1; i < n; ++i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
        w[0] = 1;
        w[1] = Pow(3, (MOD - 1) / n);
        for (int i = 2; i < n; ++i)
            w[i] = Mul(w[i - 1], w[1]);
        return;
    }

    void DFT(vector &a, int k) {
        static int _k = 0;
        static int _rev[N * 2], _w[N * 2];
        for (; _k <= k; ++_k)
            Init(_k, _rev + (1 << _k), _w + (1 << _k));
        int *rev = &_rev[1 << k];
        int n = 1 << k;
        for (int i = 0; i < n; ++i)
            if (i < rev[i]) swap(a[i], a[rev[i]]);
        for (int l = 1; l <= k; ++l) {
            int m = 1 << (l - 1);
            int *w = &_w[1 << l];
            for (vector :: iterator p = a.begin(); p != a.begin() + n; p += 1 << l)
                for (int i = 0; i < m; ++i) {
                    int t = Mul(p[m + i], w[i]);
                    p[m + i] = Sub(p[i], t);
                    p[i] = Add(p[i], t);
                }
        }
        return;
    }

    void IDFT(vector &a, int k) {
        DFT(a, k);
        int n = 1 << k;
        reverse(a.begin() + 1, a.begin() + n);
        int inv = Pow(n, MOD - 2);
        for (int i = 0; i < n; ++i)
            a[i] = Mul(a[i], inv);
        return;
    }

    vector Multiply(vector a, vector b) {
        int _n = (int)a.size() - 1, _m = (int)b.size() - 1;
        int k = 0;
        for (; (1 << k) < _n + _m + 1; ++k);
        int n = 1 << k;
        a.resize(n);
        b.resize(n);
        DFT(a, k);
        DFT(b, k);
        for (int i = 0; i < n; ++i)
            a[i] = Mul(a[i], b[i]);
        IDFT(a, k);
        a.resize(_n + _m + 1);
        return a;
    }

    vector Reciprocal(vector a) {
        if (!a[0]) {
            cerr << "irreversible" << endl;
            throw;
        }
        int _n = (int)a.size();
        vector b(1, Pow(a[0], MOD - 2)), c;
        for (int n = 1, k = 0; n < _n; ) {
            n <<= 1;
            ++k;
            b.resize(n << 1);
            c.resize(n << 1);
            for (int i = 0; i < n; ++i)
                c[i] = (i < _n) ? a[i] : 0;
            DFT(b, k + 1);
            DFT(c, k + 1);
            for (int i = 0; i < (n << 1); ++i)
                b[i] = Mul(b[i], Sub(2, Mul(b[i], c[i])));
            IDFT(b, k + 1);
            b.resize(n);
            // fill(b.begin() + n, b.end(), 0);
        }
        b.resize(_n);
        return b;
    }

    vector Addition(vector a, vector b) {
        if (a.size() < b.size()) swap(a, b);
        int m = b.size();
        for (int i = 0; i < m; ++i)
            a[i] = Add(a[i], b[i]);
        return a;
    }

    vector Subtract(vector a, vector b) {
        if (a.size() < b.size()) swap(a, b);
        int m = b.size();
        for (int i = 0; i < m; ++i)
            a[i] = Sub(a[i], b[i]);
        return a;
    }

    vector Divide(vector a, vector b) {
        int n = (int)a.size() - 1, m = (int)b.size() - 1;
        if (n < m) return vector(1);
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        a.resize(n - m + 1);
        b.resize(n - m + 1);
        a = Multiply(a, Reciprocal(b));
        a.resize(n - m + 1);
        reverse(a.begin(), a.end());
        return a;
    }

    vector Module(vector a, vector b) {
        int n = (int)a.size() - 1, m = (int)b.size() - 1;
        if (n < m) return a;
        a = Subtract(a, Multiply(Divide(a, b), b));
        a.resize(m);
        return a;
    }
    
}

const int M = 64005;

int n, m;
vector a;
int b[M];

int res[M];
vector v[M * 4];

void Build(int k, int l, int r) {
    if (l == r) {
        v[k].push_back(Sub(0, b[l]));
        v[k].push_back(1);
        return;
    }
    int m = (l + r) / 2;
    Build(k << 1, l, m);
    Build(k << 1 | 1, m + 1, r);
    v[k] = Poly::Multiply(v[k << 1], v[k << 1 | 1]);
    return;
}

void Divide(int k, int l, int r, vector a) {
    a = Poly::Module(a, v[k]);
    if (l == r) {
        res[l] = a[0];
        return;
    }
    int m = (l + r) / 2;
    Divide(k << 1, l, m, a);
    Divide(k << 1 | 1, m + 1, r, a);
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    a.resize(n + 1);
    for (int i = 0; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%d", &b[i]);
    Build(1, 1, m);
    Divide(1, 1, m, a);
    for (int i = 1; i <= m; ++i)
        printf("%d\n", res[i]);
    return 0;
}