博主最近心血来潮，贴贴全家桶。
本多项式全家桶包含了：多项式乘法，多项式求逆，多项式求ln，多项式求exp，多项式除法，多项式取模，多项式多点求值，以及一个为了多点求值用的分治NTT。
由于时代变了，博主的多点求值使用了常数较小的版本。
#include <bits/stdc++.h>
#define I inline
#define fi first
#define se second
#define LL long long
#define mp make_pair
#define pii pair<int,int>
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define fd(i, a, b) for(int i = a; i >= b; i--)
#define ULL unsigned long long
using namespace std;
const int inf = 2147483647;
const int mod = 998244353;
const int N = 1 << 17;
I int _max(int x, int y) {return x > y ? x : y;}
I int _min(int x, int y) {return x < y ? x : y;}
I LL read() {
LL x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x * f;
}
I void ptt(LL x) {if(x >= 10) ptt(x / 10); putchar(x % 10 + '0');}
I void put(LL x) {x < 0 ? putchar('-'), ptt(-x) : ptt(x);}
I void pr1(LL x) {put(x), putchar(' ');}
I void pr2(LL x) {put(x), puts("");}
I int pow_mod(int a, int k) {int ans = 1; for(; k; k >>= 1, a = (LL)a * a % mod) if(k & 1) ans = (LL)ans * a % mod; return ans;}
namespace Poly {
int jc[N], inv[N], iv[N];
int w[N << 1], R[N << 1], h[N << 1]; ULL p[N << 1];
int cnt; vector<int> q[N << 2], o[N << 2];
I int Pre(int n) {
int len = 1; for(; len <= n; len <<= 1);
iv[0] = iv[1] = 1; fo(i, 2, n) iv[i] = (LL)iv[mod % i] * (mod - mod / i) % mod;
jc[0] = 1; fo(i, 1, n) jc[i] = (LL)jc[i - 1] * i % mod;
inv[n] = pow_mod(jc[n], mod - 2); fd(i, n, 1) inv[i - 1] = (LL)inv[i] * i % mod;
for(int i = 1; i < (len << 1); i <<= 1) {
int s = 1, wn = pow_mod(3, (mod - 1) / (i << 1));
fo(j, 0, i - 1) w[i + j] = s, s = (LL)s * wn % mod;
} return len;
}
I int pre(int n) {
int len = 1; for(; len <= n; len <<= 1);
fo(i, 0, len - 1) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (len >> 1) : 0);
return len;
}
I int gao(int x) {return x < 0 ? x + mod : x;}
I void DFT(int y[], int len) {
fo(i, 0, len - 1) p[R[i]] = gao(y[i]);
int b;
for(int i = 1; i < len; i <<= 1) for(int j = 0; j < len; j += i << 1)
fo(k, 0, i - 1) b = p[j + k + i] * w[i + k] % mod, p[j + k + i] = p[j + k] + mod - b, p[j + k] = p[j + k] + b;
fo(i, 0, len - 1) y[i] = p[i] % mod;
}
I void IDFT(int y[], int len) {
reverse(y + 1, y + len); DFT(y, len); int hh = pow_mod(len, mod - 2);
fo(i, 0, len - 1) y[i] = (LL)y[i] * hh % mod;
}
I void clear(int y[], int len) {fo(i, len, (len << 1) - 1) y[i] = 0;}
I void clear(int a[], int s, int t) {if(s >= t) return ; memset(a + s, 0, sizeof(a[0]) * (t - s));}
I void cpy(int a[], int b[], int len) {memcpy(a, b, sizeof(a[0]) * len), memset(a + len, 0, sizeof(a[0]) * len);}
I void cpy(int a[], vector<int> b) {fo(i, 0, (int)b.size() - 1) a[i] = b[i];}
I void cpy(vector<int> &a, int b[], int len) {a.resize(len); fo(i, 0, len - 1) a[i] = b[i];}
I void getinv(int a[], int b[], int len) {
if(len == 1) {b[0] = pow_mod(a[0], mod - 2), b[1] = 0; return ;}
getinv(a, b, len >> 1); cpy(h, a, len), clear(b, len);
fo(i, 0, (len << 1) - 1) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? len : 0);
DFT(h, len << 1), DFT(b, len << 1);
fo(i, 0, (len << 1) - 1) b[i] = (2 - (LL)b[i] * h[i]) % mod * b[i] % mod;
IDFT(b, len << 1); clear(b, len);
}
I void getln(int a[], int b[], int len) {
getinv(a, b, len);
fo(i, 1, len - 1) h[i - 1] = (LL)a[i] * i % mod; h[len - 1] = 0; clear(h, len);
DFT(h, len << 1), DFT(b, len << 1); fo(i, 0, (len << 1) - 1) b[i] = (LL)h[i] * b[i] % mod;
IDFT(b, len << 1); fd(i, len - 1, 1) b[i] = (LL)b[i - 1] * iv[i] % mod; clear(b, len), b[0] = 0;
}
const int Z = 16;
int MEM1[N * 10], z[N << 1]; ULL MEM2[N * 10], g[N << 1];
I void solve(int l, int r, int *MEMP1, ULL *MEMP2) {
if(r - l + 1 <= 64) {
fo(i, l, r) g[i] %= mod;
fo(i, l, r) {
if(i == 0) g[i] = 1;
else g[i] = g[i] % mod * iv[i] % mod;
fo(j, i + 1, r) g[j] += g[i] * z[j - i];
if(i & 15) fo(j, i + 1, r) g[j] %= mod;
} return ;
} int len = (r - l + 1) / Z, ll = len << 1;
fo(i, 0, ll - 1) R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (ll >> 1) : 0);
int *h1[Z]; ULL *h2[Z];
fo(i, 0, Z - 1) {
h1[i] = MEMP1; MEMP1 += ll;
h2[i] = MEMP2; MEMP2 += ll;
fo(j, 0, ll - 1) h2[i][j] = 0;
} if(l == 0) {
fo(i, 0, Z - 2) {
fo(j, 0, ll - 1) h1[i][j] = z[j + i * len];
DFT(h1[i], ll);
}
} fo(i, 0, Z - 1) {
fo(j, 0, ll - 1) h1[Z - 1][j] = h2[i][j] % mod;
IDFT(h1[Z - 1], ll);
fo(j, 0, len - 1) g[l + i * len + j] += h1[Z - 1][j + len];
solve(l + i * len, l + (i + 1) * len - 1, MEMP1, MEMP2);
if(i == Z - 1) return ;
fo(j, 0, ll - 1) R[j] = (R[j >> 1] >> 1) | ((j & 1) ? (ll >> 1) : 0), h1[Z - 1][j] = 0;
fo(j, 0, len - 1) h1[Z - 1][j] = g[l + i * len + j];
DFT(h1[Z - 1], ll);
fo(j, i + 1, Z - 1) fo(k, 0, ll - 1) h2[j][k] += (LL)h1[Z - 1][k] * h1[j - i - 1][k];
}
}
I void getexp(int a[], int b[], int len) {
fo(i, 0, len - 1) z[i] = (LL)i * a[i] % mod, g[i] = 0;
solve(0, len - 1, MEM1, MEM2);
fo(i, 0, len - 1) b[i] = g[i];
}
int C[N << 1];
I void getpw(int a[], int b[], int k, int len) {
getln(a, C, len);
fo(i, 0, len - 1) C[i] = (LL)C[i] * k % mod;
getexp(C, b, len);
}
int V[N << 1];
I void mul(int a[], int b[], int len1, int len2) {
int len = pre(len1 + len2 - 1);
if(len1 + len2 - 1 <= 64) {
clear(V, 0, len1 + len2 - 1);
fo(i, 0, len1 - 1) fo(j, 0, len2 - 1) V[i + j] = (V[i + j] + (LL)a[i] * b[j]) % mod;
cpy(a, V, len1 + len2 - 1), clear(a + len1 + len2 - 1, len);
return ;
}
cpy(V, b, len2), clear(a, len1, len), clear(V, len2, len);
DFT(a, len), DFT(V, len);
fo(i, 0, len - 1) a[i] = (LL)a[i] * V[i] % mod;
IDFT(a, len); clear(a, len1 + len2 - 1, len);
}
I void MULT(int a[], int b[], int len1, int len2) {
int len = pre(len1);
if(len1 <= 64) {
clear(V, 0, len1 - len2 + 1);
fo(i, 0, len1 - len2) {
fo(j, 0, min(len2 - 1, len1 - i - 1)) V[i] = (V[i] + (LL)a[i + j] * b[j]) % mod;
} cpy(a, V, len1 - len2 + 1), clear(a, len1 - len2 + 1, len);
return ;
}
cpy(V, b, len2), reverse(V, V + len2), clear(V, len2, len), clear(a, len1, len);
DFT(a, len), DFT(V, len);
fo(i, 0, len - 1) a[i] = (LL)a[i] * V[i] % mod;
IDFT(a, len); fo(i, 0, len1 - len2) a[i] = a[i + len2 - 1]; clear(a, len1 - len2 + 1, len);
}
int h1[N << 1], h2[N << 1];
I void getdiv(int a[], int b[], int c[], int n, int m) {
int ln = n - m + 1, len = pre(ln); cpy(h1, a, n), cpy(h2, b, m);
reverse(h1, h1 + n), reverse(h2, h2 + m), clear(h2, m, len);
getinv(h2, c, len), mul(c, h1, ln, ln), reverse(c, c + ln);
}
I void getmod(int a[], int b[], int c[], int n, int m) {
if(n < m) return ;
getdiv(a, b, c, n, m);
mul(c, b, n - m + 1, m);
fo(i, 0, n - 1) c[i] = (a[i] - c[i]) % mod;
}
vector<int> G[N << 1], F[N << 1]; int d[N], A[N << 1], B[N << 1];
I void gao1(int u, int l, int r) {
if(l == r) {
G[u].push_back(1), G[u].push_back(gao(-d[l]));
G[u].resize(2);
return ;
} int mid = l + r >> 1;
gao1(u << 1, l, mid), gao1(u << 1 | 1, mid + 1, r);
cpy(A, G[u << 1]), cpy(B, G[u << 1 | 1]);
mul(A, B, mid - l + 2, r - mid + 1);
cpy(G[u], A, r - l + 2);
}
I void gao2(int u, int l, int r) {
if(l == r) {d[l] = F[u][0]; return ;}
int mid = l + r >> 1;
cpy(A, F[u]), cpy(B, G[u << 1 | 1]);
MULT(A, B, r - l + 2, r - mid + 1);
cpy(F[u << 1], A, mid - l + 2);
cpy(A, F[u]), cpy(B, G[u << 1]);
MULT(A, B, r - l + 2, mid - l + 2);
cpy(F[u << 1 | 1], A, r - mid + 1);
gao2(u << 1, l, mid), gao2(u << 1 | 1, mid + 1, r);
}
I void getval(int a[], int b[], int n, int m) {
fo(i, 1, m) d[i] = b[i];
gao1(1, 1, m);
cpy(A, G[1]);
int len = pre(n + 1);
getinv(A, B, len); reverse(B, B + n + 1);
fo(i, 0, n) A[i] = a[i];
mul(A, B, n + 1, n + 1);
F[1].resize(m + 1);
fo(i, 0, m) F[1][i] = A[i + n];
gao2(1, 1, m);
fo(i, 1, m) b[i] = d[i];
}
}
int main() {
return 0;
}