存档
#include <iostream>
#include <vector>
using namespace std;
using i64 = long long;
const int N = 1000010;
const int mod = 998244353;
const int g = 3, invg = 332748118;
int a[N], b[N];
int r[N], tot, bit;
int n, m;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
void NTT(int a[], int inv) {
for (int i = 0; i < tot; i++)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int mid = 1; mid < tot; mid <<= 1) {
int g1 = qpow(inv == 1 ? g : invg, (mod - 1) / (mid << 1));
for (int i = 0; i < tot; i += mid << 1) {
for (int j = 0, gk = 1; j < mid; j++, gk = 1ll * gk * g1 % mod) {
int x = a[i + j], y = 1ll * gk * a[i + j + mid] % mod;
a[i + j] = (x + y) % mod, a[i + j + mid] = (x - y + mod) % mod;
}
}
}
}
struct Poly {
vector<int> coef;
int deg;
Poly(int deg = -1) : deg(deg) {
coef = vector<int>(deg + 1, 0);
}
} p[N];
Poly operator+ (const Poly& A, const Poly& B) {
Poly res(max(A.deg, B.deg));
for (int i = 0; i <= res.deg; i++) {
if (i <= A.deg) res.coef[i] += A.coef[i];
if (i <= B.deg) res.coef[i] += B.coef[i];
res.coef[i] %= mod;
}
return res;
}
Poly operator- (const Poly& A, const Poly& B) {
Poly res(max(A.deg, B.deg));
for (int i = 0; i <= res.deg; i++) {
if (i <= A.deg) res.coef[i] -= A.coef[i];
if (i <= B.deg) res.coef[i] -= B.coef[i];
res.coef[i] = (res.coef[i] + 2 * mod) % mod;
}
return res;
}
Poly operator* (const Poly& A, int k) {
Poly res(A.deg);
for (int i = 0; i <= A.deg; i++) {
res.coef[i] = (1ll * k * A.coef[i]) % mod;
}
return res;
}
Poly operator* (const Poly& A, const Poly& B) {
Poly res(A.deg + B.deg);
bit = tot = 0;
while ((1 << bit) <= res.deg) bit++;
tot = 1 << bit;
for (int i = 0; i < tot; i++) a[i] = b[i] = 0;
for (int i = 0; i <= A.deg; i++) a[i] = A.coef[i];
for (int i = 0; i <= B.deg; i++) b[i] = B.coef[i];
for (int i = 1; i < tot; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (bit - 1));
NTT(a, 1), NTT(b, 1);
for (int i = 0; i < tot; i++) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, -1);
int totinv = qpow(tot, mod - 2);
for (int i = 0; i <= res.deg; i++) res.coef[i] = 1ll * a[i] * totinv % mod;
return res;
}
Poly solve(int l, int r) {
if (l == r) return p[l];
int mid = l + r >> 1;
return solve(l, mid) * solve(mid + 1, r);
}
int fac[N], invfac[N];
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
invfac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; i--)
invfac[i] = 1ll * invfac[i + 1] * (i + 1) % mod;
};
int binom(int a, int b) {
return 1ll * fac[a] * invfac[b] % mod * invfac[a - b] % mod;
}
int main() {
return 0;
}