結果
問題 | No.2166 Paint and Fill |
ユーザー | 👑 hos.lyric |
提出日時 | 2022-12-18 07:21:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 62,482 bytes |
コンパイル時間 | 7,473 ms |
コンパイル使用メモリ | 409,776 KB |
実行使用メモリ | 43,956 KB |
最終ジャッジ日時 | 2024-11-17 16:32:49 |
合計ジャッジ時間 | 188,711 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
31,876 KB |
testcase_01 | AC | 547 ms
43,956 KB |
testcase_02 | TLE | - |
testcase_03 | AC | 303 ms
32,004 KB |
testcase_04 | AC | 297 ms
32,064 KB |
testcase_05 | AC | 289 ms
31,768 KB |
testcase_06 | AC | 300 ms
32,008 KB |
testcase_07 | AC | 290 ms
32,004 KB |
testcase_08 | AC | 4,006 ms
32,136 KB |
testcase_09 | AC | 3,998 ms
32,136 KB |
testcase_10 | AC | 3,953 ms
32,268 KB |
testcase_11 | AC | 3,984 ms
32,052 KB |
testcase_12 | AC | 3,933 ms
16,324 KB |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | AC | 21 ms
16,068 KB |
testcase_26 | AC | 20 ms
16,000 KB |
testcase_27 | AC | 1,306 ms
27,860 KB |
testcase_28 | AC | 1,392 ms
28,024 KB |
testcase_29 | AC | 1,056 ms
27,964 KB |
testcase_30 | AC | 1,011 ms
27,900 KB |
testcase_31 | AC | 1,003 ms
28,016 KB |
testcase_32 | AC | 1,540 ms
28,080 KB |
testcase_33 | AC | 539 ms
28,028 KB |
testcase_34 | AC | 1,026 ms
28,096 KB |
testcase_35 | AC | 1,019 ms
27,960 KB |
testcase_36 | AC | 1,553 ms
28,024 KB |
testcase_37 | AC | 1,009 ms
28,024 KB |
testcase_38 | AC | 2,060 ms
28,020 KB |
testcase_39 | AC | 1,537 ms
43,768 KB |
コンパイルメッセージ
template/template.hpp: In function 'int nyaan::main()': template/template.hpp:74:30: warning: no return statement in function returning non-void [-Wreturn-type]
ソースコード
// TODO: my own library // Nyaan orz // used https://nyaannyaan.github.io/library/verify/verify-unit-test/polynomial-matrix-prod.test.cpp #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } //////////////////////////////////////////////////////////////////////////////// template <unsigned M_> struct ModInt { static constexpr unsigned M = M_; unsigned x; constexpr ModInt() : x(0U) {} constexpr ModInt(unsigned x_) : x(x_ % M) {} constexpr ModInt(unsigned long long x_) : x(x_ % M) {} constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {} constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {} ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; } ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; } ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; } ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); } ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b; } ModInt inv() const { unsigned a = M, b = x; int y = 0, z = 1; for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; } assert(a == 1U); return ModInt(y); } ModInt operator+() const { return *this; } ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; } ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); } ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); } ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); } ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); } template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); } template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); } template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); } template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); } explicit operator bool() const { return x; } bool operator==(const ModInt &a) const { return (x == a.x); } bool operator!=(const ModInt &a) const { return (x != a.x); } friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; } }; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// constexpr unsigned MO = 998244353U; constexpr unsigned MO2 = 2U * MO; constexpr int FFT_MAX = 23; using Mint = ModInt<MO>; constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U}; constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U}; constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U}; constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U}; // as[rev(i)] <- \sum_j \zeta^(ij) as[j] void fft(Mint *as, int n) { assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX); int m = n; if (m >>= 1) { for (int i = 0; i < m; ++i) { const unsigned x = as[i + m].x; // < MO as[i + m].x = as[i].x + MO - x; // < 2 MO as[i].x += x; // < 2 MO } } if (m >>= 1) { Mint prod = 1U; for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) { for (int i = i0; i < i0 + m; ++i) { const unsigned x = (prod * as[i + m]).x; // < MO as[i + m].x = as[i].x + MO - x; // < 3 MO as[i].x += x; // < 3 MO } prod *= FFT_RATIOS[__builtin_ctz(++h)]; } } for (; m; ) { if (m >>= 1) { Mint prod = 1U; for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) { for (int i = i0; i < i0 + m; ++i) { const unsigned x = (prod * as[i + m]).x; // < MO as[i + m].x = as[i].x + MO - x; // < 4 MO as[i].x += x; // < 4 MO } prod *= FFT_RATIOS[__builtin_ctz(++h)]; } } if (m >>= 1) { Mint prod = 1U; for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) { for (int i = i0; i < i0 + m; ++i) { const unsigned x = (prod * as[i + m]).x; // < MO as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO as[i + m].x = as[i].x + MO - x; // < 3 MO as[i].x += x; // < 3 MO } prod *= FFT_RATIOS[__builtin_ctz(++h)]; } } } for (int i = 0; i < n; ++i) { as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x; // < MO } } // as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)] void invFft(Mint *as, int n) { assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX); int m = 1; if (m < n >> 1) { Mint prod = 1U; for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) { for (int i = i0; i < i0 + m; ++i) { const unsigned long long y = as[i].x + MO - as[i + m].x; // < 2 MO as[i].x += as[i + m].x; // < 2 MO as[i + m].x = (prod.x * y) % MO; // < MO } prod *= INV_FFT_RATIOS[__builtin_ctz(++h)]; } m <<= 1; } for (; m < n >> 1; m <<= 1) { Mint prod = 1U; for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) { for (int i = i0; i < i0 + (m >> 1); ++i) { const unsigned long long y = as[i].x + MO2 - as[i + m].x; // < 4 MO as[i].x += as[i + m].x; // < 4 MO as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO as[i + m].x = (prod.x * y) % MO; // < MO } for (int i = i0 + (m >> 1); i < i0 + m; ++i) { const unsigned long long y = as[i].x + MO - as[i + m].x; // < 2 MO as[i].x += as[i + m].x; // < 2 MO as[i + m].x = (prod.x * y) % MO; // < MO } prod *= INV_FFT_RATIOS[__builtin_ctz(++h)]; } } if (m < n) { for (int i = 0; i < m; ++i) { const unsigned y = as[i].x + MO2 - as[i + m].x; // < 4 MO as[i].x += as[i + m].x; // < 4 MO as[i + m].x = y; // < 4 MO } } const Mint invN = Mint(n).inv(); for (int i = 0; i < n; ++i) { as[i] *= invN; } } void fft(vector<Mint> &as) { fft(as.data(), as.size()); } void invFft(vector<Mint> &as) { invFft(as.data(), as.size()); } vector<Mint> convolve(vector<Mint> as, vector<Mint> bs) { if (as.empty() || bs.empty()) return {}; const int len = as.size() + bs.size() - 1; int n = 1; for (; n < len; n <<= 1) {} as.resize(n); fft(as); bs.resize(n); fft(bs); for (int i = 0; i < n; ++i) as[i] *= bs[i]; invFft(as); as.resize(len); return as; } vector<Mint> square(vector<Mint> as) { if (as.empty()) return {}; const int len = as.size() + as.size() - 1; int n = 1; for (; n < len; n <<= 1) {} as.resize(n); fft(as); for (int i = 0; i < n; ++i) as[i] *= as[i]; invFft(as); as.resize(len); return as; } //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// // inv: log, exp, pow // fac: shift // invFac: shift constexpr int LIM_INV = 1 << 20; // @ Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV]; struct ModIntPreparator { ModIntPreparator() { inv[1] = 1; for (int i = 2; i < LIM_INV; ++i) inv[i] = -((Mint::M / i) * inv[Mint::M % i]); fac[0] = 1; for (int i = 1; i < LIM_INV; ++i) fac[i] = fac[i - 1] * i; invFac[0] = 1; for (int i = 1; i < LIM_INV; ++i) invFac[i] = invFac[i - 1] * inv[i]; } } preparator; // polyWork0: *, inv, div, divAt, log, exp, pow, sqrt, shift // polyWork1: inv, div, divAt, log, exp, pow, sqrt, shift // polyWork2: divAt, exp, pow, sqrt // polyWork3: exp, pow, sqrt static constexpr int LIM_POLY = 1 << 20; // @ static_assert(LIM_POLY <= 1 << FFT_MAX, "Poly: LIM_POLY <= 1 << FFT_MAX must hold."); static Mint polyWork0[LIM_POLY], polyWork1[LIM_POLY], polyWork2[LIM_POLY], polyWork3[LIM_POLY]; struct Poly : public vector<Mint> { Poly() {} explicit Poly(int n) : vector<Mint>(n) {} Poly(const vector<Mint> &vec) : vector<Mint>(vec) {} Poly(std::initializer_list<Mint> il) : vector<Mint>(il) {} int size() const { return vector<Mint>::size(); } Mint at(long long k) const { return (0 <= k && k < size()) ? (*this)[k] : 0U; } int ord() const { for (int i = 0; i < size(); ++i) if ((*this)[i]) return i; return -1; } int deg() const { for (int i = size(); --i >= 0; ) if ((*this)[i]) return i; return -1; } Poly mod(int n) const { return Poly(vector<Mint>(data(), data() + min(n, size()))); } friend std::ostream &operator<<(std::ostream &os, const Poly &fs) { os << "["; for (int i = 0; i < fs.size(); ++i) { if (i > 0) os << ", "; os << fs[i]; } return os << "]"; } Poly &operator+=(const Poly &fs) { if (size() < fs.size()) resize(fs.size()); for (int i = 0; i < fs.size(); ++i) (*this)[i] += fs[i]; return *this; } Poly &operator-=(const Poly &fs) { if (size() < fs.size()) resize(fs.size()); for (int i = 0; i < fs.size(); ++i) (*this)[i] -= fs[i]; return *this; } // 3 E(|t| + |f|) Poly &operator*=(const Poly &fs) { if (empty() || fs.empty()) return *this = {}; const int nt = size(), nf = fs.size(); int n = 1; for (; n < nt + nf - 1; n <<= 1) {} assert(n <= LIM_POLY); resize(n); fft(data(), n); // 1 E(n) memcpy(polyWork0, fs.data(), nf * sizeof(Mint)); memset(polyWork0 + nf, 0, (n - nf) * sizeof(Mint)); fft(polyWork0, n); // 1 E(n) for (int i = 0; i < n; ++i) (*this)[i] *= polyWork0[i]; invFft(data(), n); // 1 E(n) resize(nt + nf - 1); return *this; } // 13 E(deg(t) - deg(f) + 1) // rev(t) = rev(f) rev(q) + x^(deg(t)-deg(f)+1) rev(r) Poly &operator/=(const Poly &fs) { const int m = deg(), n = fs.deg(); assert(n != -1); if (m < n) return *this = {}; Poly tsRev(m - n + 1), fsRev(min(m - n, n) + 1); for (int i = 0; i <= m - n; ++i) tsRev[i] = (*this)[m - i]; for (int i = 0, i0 = min(m - n, n); i <= i0; ++i) fsRev[i] = fs[n - i]; const Poly qsRev = tsRev.div(fsRev, m - n + 1); // 13 E(m - n + 1) resize(m - n + 1); for (int i = 0; i <= m - n; ++i) (*this)[i] = qsRev[m - n - i]; return *this; } // 13 E(deg(t) - deg(f) + 1) + 3 E(|t|) Poly &operator%=(const Poly &fs) { const Poly qs = *this / fs; // 13 E(deg(t) - deg(f) + 1) *this -= fs * qs; // 3 E(|t|) resize(deg() + 1); return *this; } Poly &operator*=(const Mint &a) { for (int i = 0; i < size(); ++i) (*this)[i] *= a; return *this; } Poly &operator/=(const Mint &a) { const Mint b = a.inv(); for (int i = 0; i < size(); ++i) (*this)[i] *= b; return *this; } Poly operator+() const { return *this; } Poly operator-() const { Poly fs(size()); for (int i = 0; i < size(); ++i) fs[i] = -(*this)[i]; return fs; } Poly operator+(const Poly &fs) const { return (Poly(*this) += fs); } Poly operator-(const Poly &fs) const { return (Poly(*this) -= fs); } Poly operator*(const Poly &fs) const { return (Poly(*this) *= fs); } Poly operator/(const Poly &fs) const { return (Poly(*this) /= fs); } Poly operator%(const Poly &fs) const { return (Poly(*this) %= fs); } Poly operator*(const Mint &a) const { return (Poly(*this) *= a); } Poly operator/(const Mint &a) const { return (Poly(*this) /= a); } friend Poly operator*(const Mint &a, const Poly &fs) { return fs * a; } // 10 E(n) // f <- f - (t f - 1) f Poly inv(int n) const { assert(!empty()); assert((*this)[0]); assert(1 <= n); assert(n == 1 || 1 << (32 - __builtin_clz(n - 1)) <= LIM_POLY); Poly fs(n); fs[0] = (*this)[0].inv(); for (int m = 1; m < n; m <<= 1) { memcpy(polyWork0, data(), min(m << 1, size()) * sizeof(Mint)); memset(polyWork0 + min(m << 1, size()), 0, ((m << 1) - min(m << 1, size())) * sizeof(Mint)); fft(polyWork0, m << 1); // 2 E(n) memcpy(polyWork1, fs.data(), min(m << 1, n) * sizeof(Mint)); memset(polyWork1 + min(m << 1, n), 0, ((m << 1) - min(m << 1, n)) * sizeof(Mint)); fft(polyWork1, m << 1); // 2 E(n) for (int i = 0; i < m << 1; ++i) polyWork0[i] *= polyWork1[i]; invFft(polyWork0, m << 1); // 2 E(n) memset(polyWork0, 0, m * sizeof(Mint)); fft(polyWork0, m << 1); // 2 E(n) for (int i = 0; i < m << 1; ++i) polyWork0[i] *= polyWork1[i]; invFft(polyWork0, m << 1); // 2 E(n) for (int i = m, i0 = min(m << 1, n); i < i0; ++i) fs[i] = -polyWork0[i]; } return fs; } // 13 E(n) // g = (1 / f) mod x^m // h <- h - (f h - t) g Poly div(const Poly &fs, int n) const { assert(!fs.empty()); assert(fs[0]); assert(1 <= n); if (n == 1) return {at(0) / fs[0]}; // m < n <= 2 m const int m = 1 << (31 - __builtin_clz(n - 1)); assert(m << 1 <= LIM_POLY); Poly gs = fs.inv(m); // 5 E(n) gs.resize(m << 1); fft(gs.data(), m << 1); // 1 E(n) memcpy(polyWork0, data(), min(m, size()) * sizeof(Mint)); memset(polyWork0 + min(m, size()), 0, ((m << 1) - min(m, size())) * sizeof(Mint)); fft(polyWork0, m << 1); // 1 E(n) for (int i = 0; i < m << 1; ++i) polyWork0[i] *= gs[i]; invFft(polyWork0, m << 1); // 1 E(n) Poly hs(n); memcpy(hs.data(), polyWork0, m * sizeof(Mint)); memset(polyWork0 + m, 0, m * sizeof(Mint)); fft(polyWork0, m << 1); // 1 E(n) memcpy(polyWork1, fs.data(), min(m << 1, fs.size()) * sizeof(Mint)); memset(polyWork1 + min(m << 1, fs.size()), 0, ((m << 1) - min(m << 1, fs.size())) * sizeof(Mint)); fft(polyWork1, m << 1); // 1 E(n) for (int i = 0; i < m << 1; ++i) polyWork0[i] *= polyWork1[i]; invFft(polyWork0, m << 1); // 1 E(n) memset(polyWork0, 0, m * sizeof(Mint)); for (int i = m, i0 = min(m << 1, size()); i < i0; ++i) polyWork0[i] -= (*this)[i]; fft(polyWork0, m << 1); // 1 E(n) for (int i = 0; i < m << 1; ++i) polyWork0[i] *= gs[i]; invFft(polyWork0, m << 1); // 1 E(n) for (int i = m; i < n; ++i) hs[i] = -polyWork0[i]; return hs; } }; struct SubproductTree { int logN, n, nn; vector<Mint> xs; // [DFT_4((X-xs[0])(X-xs[1])(X-xs[2])(X-xs[3]))] [(X-xs[0])(X-xs[1])(X-xs[2])(X-xs[3])mod X^4] // [ DFT_4((X-xs[0])(X-xs[1])) ] [ DFT_4((X-xs[2])(X-xs[3])) ] // [ DFT_2(X-xs[0]) ] [ DFT_2(X-xs[1]) ] [ DFT_2(X-xs[2]) ] [ DFT_2(X-xs[3]) ] vector<Mint> buf; vector<Mint *> gss; // (1 - xs[0] X) ... (1 - xs[nn-1] X) Poly all; // (ceil(log_2 n) + O(1)) E(n) SubproductTree(const vector<Mint> &xs_) { n = xs_.size(); for (logN = 0, nn = 1; nn < n; ++logN, nn <<= 1) {} xs.assign(nn, 0U); memcpy(xs.data(), xs_.data(), n * sizeof(Mint)); buf.assign((logN + 1) * (nn << 1), 0U); gss.assign(nn << 1, nullptr); for (int h = 0; h <= logN; ++h) for (int u = 1 << h; u < 1 << (h + 1); ++u) { gss[u] = buf.data() + (h * (nn << 1) + ((u - (1 << h)) << (logN - h + 1))); } for (int i = 0; i < nn; ++i) { gss[nn + i][0] = -xs[i] + 1; gss[nn + i][1] = -xs[i] - 1; } if (nn == 1) gss[1][1] += 2; for (int h = logN; --h >= 0; ) { const int m = 1 << (logN - h); for (int u = 1 << (h + 1); --u >= 1 << h; ) { for (int i = 0; i < m; ++i) gss[u][i] = gss[u << 1][i] * gss[u << 1 | 1][i]; memcpy(gss[u] + m, gss[u], m * sizeof(Mint)); invFft(gss[u] + m, m); // ((1/2) ceil(log_2 n) + O(1)) E(n) if (h > 0) { gss[u][m] -= 2; const Mint a = FFT_ROOTS[logN - h + 1]; Mint aa = 1; for (int i = m; i < m << 1; ++i) { gss[u][i] *= aa; aa *= a; }; fft(gss[u] + m, m); // ((1/2) ceil(log_2 n) + O(1)) E(n) } } } all.resize(nn + 1); all[0] = 1; for (int i = 1; i < nn; ++i) all[i] = gss[1][nn + nn - i]; all[nn] = gss[1][nn] - 1; } // ((3/2) ceil(log_2 n) + O(1)) E(n) + 10 E(|f|) + 3 E(|f| + 2^(ceil(log_2 n))) vector<Mint> multiEval(const Poly &fs) const { vector<Mint> work0(nn), work1(nn), work2(nn); { const int m = max(fs.size(), 1); auto invAll = all.inv(m); // 10 E(|f|) std::reverse(invAll.begin(), invAll.end()); int mm; for (mm = 1; mm < m - 1 + nn; mm <<= 1) {} invAll.resize(mm, 0U); fft(invAll); // E(|f| + 2^(ceil(log_2 n))) vector<Mint> ffs(mm, 0U); memcpy(ffs.data(), fs.data(), fs.size() * sizeof(Mint)); fft(ffs); // E(|f| + 2^(ceil(log_2 n))) for (int i = 0; i < mm; ++i) ffs[i] *= invAll[i]; invFft(ffs); // E(|f| + 2^(ceil(log_2 n))) memcpy(((logN & 1) ? work1 : work0).data(), ffs.data() + m - 1, nn * sizeof(Mint)); } for (int h = 0; h < logN; ++h) { const int m = 1 << (logN - h); for (int u = 1 << h; u < 1 << (h + 1); ++u) { Mint *hs = (((logN - h) & 1) ? work1 : work0).data() + ((u - (1 << h)) << (logN - h)); Mint *hs0 = (((logN - h) & 1) ? work0 : work1).data() + ((u - (1 << h)) << (logN - h)); Mint *hs1 = hs0 + (m >> 1); fft(hs, m); // ((1/2) ceil(log_2 n) + O(1)) E(n) for (int i = 0; i < m; ++i) work2[i] = gss[u << 1 | 1][i] * hs[i]; invFft(work2.data(), m); // ((1/2) ceil(log_2 n) + O(1)) E(n) memcpy(hs0, work2.data() + (m >> 1), (m >> 1) * sizeof(Mint)); for (int i = 0; i < m; ++i) work2[i] = gss[u << 1][i] * hs[i]; invFft(work2.data(), m); // ((1/2) ceil(log_2 n) + O(1)) E(n) memcpy(hs1, work2.data() + (m >> 1), (m >> 1) * sizeof(Mint)); } } work0.resize(n); return work0; } }; //////////////////////////////////////////////////////////////////////////////// /* constexpr int FACTORIAL_STEP = 10'000'000; constexpr ModInt<998244353> FACTORIAL[] = {1,295201906,160030060,957629942,545208507,213689172,760025067,939830261,506268060,39806322,808258749,440133909,686156489,741797144,390377694,12629586,544711799,104121967,495867250,421290700,117153405,57084755,202713771,675932866,79781699,956276337,652678397,35212756,655645460,468129309,761699708,533047427,287671032,206068022,50865043,144980423,111276893,259415897,444094191,593907889,573994984,892454686,566073550,128761001,888483202,251718753,548033568,428105027,742756734,546182474,62402409,102052166,826426395,159186619,926316039,176055335,51568171,414163604,604947226,681666415,511621808,924112080,265769800,955559118,763148293,472709375,19536133,860830935,290471030,851685235,242726978,169855231,612759169,599797734,961628039,953297493,62806842,37844313,909741023,689361523,887890124,380694152,669317759,367270918,806951470,843736533,377403437,945260111,786127243,80918046,875880304,364983542,623250998,598764068,804930040,24257676,214821357,791011898,954947696,183092975,}; template <unsigned M> ModInt<M> factorial(long long n) { assert(n >= 0); if (n >= static_cast<long long>(M)) return 0; const long long pos = n / FACTORIAL_STEP; const long long m0 = pos * FACTORIAL_STEP; const long long m1 = m0 + FACTORIAL_STEP; if (m1 < static_cast<long long>(M) && n - m0 > m1 - n) { ModInt<M> prod = 1; for (long long i = m1; i > n; ) prod *= i--; return FACTORIAL[pos + 1] / prod; } else { ModInt<M> prod = FACTORIAL[pos]; for (long long i = m0; i < n; ) prod *= ++i; return prod; } } */ #line 1 "verify/verify-unit-test/polynomial-matrix-prod.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/aplusb" // #line 2 "template/template.hpp" using namespace std; // intrinstic #include <immintrin.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cctype> #include <cfenv> #include <cfloat> #include <chrono> #include <cinttypes> #include <climits> #include <cmath> #include <complex> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <initializer_list> #include <iomanip> #include <ios> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <streambuf> #include <string> #include <tuple> #include <type_traits> #include <typeinfo> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> namespace nyaan { // utility #line 1 "template/util.hpp" namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template <typename T> using V = vector<T>; template <typename T> using VV = vector<vector<T>>; using vi = vector<int>; using vl = vector<long long>; using vd = V<double>; using vs = V<string>; using vvi = vector<vector<int>>; using vvl = vector<vector<long long>>; template <typename T, typename U> struct P : pair<T, U> { template <typename... Args> P(Args... args) : pair<T, U>(args...) {} using pair<T, U>::first; using pair<T, U>::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } }; using pl = P<ll, ll>; using pi = P<int, int>; using vp = V<pl>; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template <typename T> int sz(const T &t) { return t.size(); } template <typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template <typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template <typename T> inline T Max(const vector<T> &v) { return *max_element(begin(v), end(v)); } template <typename T> inline T Min(const vector<T> &v) { return *min_element(begin(v), end(v)); } template <typename T> inline long long Sum(const vector<T> &v) { return accumulate(begin(v), end(v), 0LL); } template <typename T> int lb(const vector<T> &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template <typename T> int ub(const vector<T> &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template <typename T, typename U> pair<T, U> mkp(const T &t, const U &u) { return make_pair(t, u); } template <typename T> vector<T> mkrui(const vector<T> &v, bool rev = false) { vector<T> ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template <typename T> vector<T> mkuni(const vector<T> &v) { vector<T> ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template <typename F> vector<int> mkord(int N, F f) { vector<int> ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template <typename T> vector<int> mkinv(vector<T> &v) { int max_val = *max_element(begin(v), end(v)); vector<int> inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan #line 58 "template/template.hpp" // bit operation #line 1 "template/bitop.hpp" namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; } template <typename T> inline int gbit(const T &a, int i) { return (a >> i) & 1; } template <typename T> inline void sbit(T &a, int i, bool b) { if (gbit(a, i) != b) a ^= T(1) << i; } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan #line 61 "template/template.hpp" // inout #line 1 "template/inout.hpp" namespace Nyaan { template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } void in() {} template <typename T, class... U> void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template <typename T, class... U, char sep = ' '> void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template <typename T, class... U, char sep = ' '> void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan #line 64 "template/template.hpp" // debug #line 1 "template/debug.hpp" namespace DebugImpl { template <typename U, typename = void> struct is_specialize : false_type {}; template <typename U> struct is_specialize< U, typename conditional<false, typename U::iterator, void>::type> : true_type {}; template <typename U> struct is_specialize< U, typename conditional<false, decltype(U::first), void>::type> : true_type {}; template <typename U> struct is_specialize<U, enable_if_t<is_integral<U>::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } void dump(const bool& t) { cerr << (t ? "true" : "false"); } template <typename U, enable_if_t<!is_specialize<U>::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template <typename T> void dump(const T& t, enable_if_t<is_integral<T>::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if constexpr (is_signed<T>::value) { if (t == -Nyaan::inf) res = "-inf"; } if constexpr (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if constexpr (is_signed<T>::value) { if (t == -Nyaan::infLL) res = "-inf"; } } if (res.empty()) res = to_string(t); cerr << res; } template <typename T, typename U> void dump(const pair<T, U>&); template <typename T> void dump(const pair<T*, int>&); template <typename T> void dump(const T& t, enable_if_t<!is_void<typename T::iterator>::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template <typename T, typename U> void dump(const pair<T, U>& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template <typename T> void dump(const pair<T*, int>& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template <typename Head, typename... Tail> void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward<Tail>(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) (void(0)) #endif #line 67 "template/template.hpp" // macro #line 1 "template/macro.hpp" #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define fi first #define se second #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) #line 70 "template/template.hpp" namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } #line 4 "verify/verify-unit-test/polynomial-matrix-prod.test.cpp" // #line 2 "fps/ntt-friendly-fps.hpp" #line 2 "ntt/ntt.hpp" template <typename mint> struct NTT { static constexpr uint32_t get_pr() { uint32_t _mod = mint::get_mod(); using u64 = uint64_t; u64 ds[32] = {}; int idx = 0; u64 m = _mod - 1; for (u64 i = 2; i * i <= m; ++i) { if (m % i == 0) { ds[idx++] = i; while (m % i == 0) m /= i; } } if (m != 1) ds[idx++] = m; uint32_t _pr = 2; while (1) { int flg = 1; for (int i = 0; i < idx; ++i) { u64 a = _pr, b = (_mod - 1) / ds[i], r = 1; while (b) { if (b & 1) r = r * a % _mod; a = a * a % _mod; b >>= 1; } if (r == 1) { flg = 0; break; } } if (flg == 1) break; ++_pr; } return _pr; }; static constexpr uint32_t mod = mint::get_mod(); static constexpr uint32_t pr = get_pr(); static constexpr int level = __builtin_ctzll(mod - 1); mint dw[level], dy[level]; void setwy(int k) { mint w[level], y[level]; w[k - 1] = mint(pr).pow((mod - 1) / (1 << k)); y[k - 1] = w[k - 1].inverse(); for (int i = k - 2; i > 0; --i) w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1]; dw[1] = w[1], dy[1] = y[1], dw[2] = w[2], dy[2] = y[2]; for (int i = 3; i < k; ++i) { dw[i] = dw[i - 1] * y[i - 2] * w[i]; dy[i] = dy[i - 1] * w[i - 2] * y[i]; } } NTT() { setwy(level); } void fft4(vector<mint> &a, int k) { if ((int)a.size() <= 1) return; if (k == 1) { mint a1 = a[1]; a[1] = a[0] - a[1]; a[0] = a[0] + a1; return; } if (k & 1) { int v = 1 << (k - 1); for (int j = 0; j < v; ++j) { mint ajv = a[j + v]; a[j + v] = a[j] - ajv; a[j] += ajv; } } int u = 1 << (2 + (k & 1)); int v = 1 << (k - 2 - (k & 1)); mint one = mint(1); mint imag = dw[1]; while (v) { // jh = 0 { int j0 = 0; int j1 = v; int j2 = j1 + v; int j3 = j2 + v; for (; j0 < v; ++j0, ++j1, ++j2, ++j3) { mint t0 = a[j0], t1 = a[j1], t2 = a[j2], t3 = a[j3]; mint t0p2 = t0 + t2, t1p3 = t1 + t3; mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag; a[j0] = t0p2 + t1p3, a[j1] = t0p2 - t1p3; a[j2] = t0m2 + t1m3, a[j3] = t0m2 - t1m3; } } // jh >= 1 mint ww = one, xx = one * dw[2], wx = one; for (int jh = 4; jh < u;) { ww = xx * xx, wx = ww * xx; int j0 = jh * v; int je = j0 + v; int j2 = je + v; for (; j0 < je; ++j0, ++j2) { mint t0 = a[j0], t1 = a[j0 + v] * xx, t2 = a[j2] * ww, t3 = a[j2 + v] * wx; mint t0p2 = t0 + t2, t1p3 = t1 + t3; mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag; a[j0] = t0p2 + t1p3, a[j0 + v] = t0p2 - t1p3; a[j2] = t0m2 + t1m3, a[j2 + v] = t0m2 - t1m3; } xx *= dw[__builtin_ctzll((jh += 4))]; } u <<= 2; v >>= 2; } } void ifft4(vector<mint> &a, int k) { if ((int)a.size() <= 1) return; if (k == 1) { mint a1 = a[1]; a[1] = a[0] - a[1]; a[0] = a[0] + a1; return; } int u = 1 << (k - 2); int v = 1; mint one = mint(1); mint imag = dy[1]; while (u) { // jh = 0 { int j0 = 0; int j1 = v; int j2 = v + v; int j3 = j2 + v; for (; j0 < v; ++j0, ++j1, ++j2, ++j3) { mint t0 = a[j0], t1 = a[j1], t2 = a[j2], t3 = a[j3]; mint t0p1 = t0 + t1, t2p3 = t2 + t3; mint t0m1 = t0 - t1, t2m3 = (t2 - t3) * imag; a[j0] = t0p1 + t2p3, a[j2] = t0p1 - t2p3; a[j1] = t0m1 + t2m3, a[j3] = t0m1 - t2m3; } } // jh >= 1 mint ww = one, xx = one * dy[2], yy = one; u <<= 2; for (int jh = 4; jh < u;) { ww = xx * xx, yy = xx * imag; int j0 = jh * v; int je = j0 + v; int j2 = je + v; for (; j0 < je; ++j0, ++j2) { mint t0 = a[j0], t1 = a[j0 + v], t2 = a[j2], t3 = a[j2 + v]; mint t0p1 = t0 + t1, t2p3 = t2 + t3; mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy; a[j0] = t0p1 + t2p3, a[j2] = (t0p1 - t2p3) * ww; a[j0 + v] = t0m1 + t2m3, a[j2 + v] = (t0m1 - t2m3) * ww; } xx *= dy[__builtin_ctzll(jh += 4)]; } u >>= 4; v <<= 2; } if (k & 1) { u = 1 << (k - 1); for (int j = 0; j < u; ++j) { mint ajv = a[j] - a[j + u]; a[j] += a[j + u]; a[j + u] = ajv; } } } void ntt(vector<mint> &a) { if ((int)a.size() <= 1) return; fft4(a, __builtin_ctz(a.size())); } void intt(vector<mint> &a) { if ((int)a.size() <= 1) return; ifft4(a, __builtin_ctz(a.size())); mint iv = mint(a.size()).inverse(); for (auto &x : a) x *= iv; } vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) { int l = a.size() + b.size() - 1; if (min<int>(a.size(), b.size()) <= 40) { vector<mint> s(l); for (int i = 0; i < (int)a.size(); ++i) for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j]; return s; } int k = 2, M = 4; while (M < l) M <<= 1, ++k; setwy(k); vector<mint> s(M), t(M); for (int i = 0; i < (int)a.size(); ++i) s[i] = a[i]; for (int i = 0; i < (int)b.size(); ++i) t[i] = b[i]; fft4(s, k); fft4(t, k); for (int i = 0; i < M; ++i) s[i] *= t[i]; ifft4(s, k); s.resize(l); mint invm = mint(M).inverse(); for (int i = 0; i < l; ++i) s[i] *= invm; return s; } void ntt_doubling(vector<mint> &a) { int M = (int)a.size(); auto b = a; intt(b); mint r = 1, zeta = mint(pr).pow((mint::get_mod() - 1) / (M << 1)); for (int i = 0; i < M; i++) b[i] *= r, r *= zeta; ntt(b); copy(begin(b), end(b), back_inserter(a)); } }; #line 2 "fps/formal-power-series.hpp" template <typename mint> struct FormalPowerSeries : vector<mint> { using vector<mint>::vector; using FPS = FormalPowerSeries; FPS &operator+=(const FPS &r) { if (r.size() > this->size()) this->resize(r.size()); for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i]; return *this; } FPS &operator+=(const mint &r) { if (this->empty()) this->resize(1); (*this)[0] += r; return *this; } FPS &operator-=(const FPS &r) { if (r.size() > this->size()) this->resize(r.size()); for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i]; return *this; } FPS &operator-=(const mint &r) { if (this->empty()) this->resize(1); (*this)[0] -= r; return *this; } FPS &operator*=(const mint &v) { for (int k = 0; k < (int)this->size(); k++) (*this)[k] *= v; return *this; } FPS &operator/=(const FPS &r) { if (this->size() < r.size()) { this->clear(); return *this; } int n = this->size() - r.size() + 1; if ((int)r.size() <= 64) { FPS f(*this), g(r); g.shrink(); mint coeff = g.back().inverse(); for (auto &x : g) x *= coeff; int deg = (int)f.size() - (int)g.size() + 1; int gs = g.size(); FPS quo(deg); for (int i = deg - 1; i >= 0; i--) { quo[i] = f[i + gs - 1]; for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j]; } *this = quo * coeff; this->resize(n, mint(0)); return *this; } return *this = ((*this).rev().pre(n) * r.rev().inv(n)).pre(n).rev(); } FPS &operator%=(const FPS &r) { *this -= *this / r * r; shrink(); return *this; } FPS operator+(const FPS &r) const { return FPS(*this) += r; } FPS operator+(const mint &v) const { return FPS(*this) += v; } FPS operator-(const FPS &r) const { return FPS(*this) -= r; } FPS operator-(const mint &v) const { return FPS(*this) -= v; } FPS operator*(const FPS &r) const { return FPS(*this) *= r; } FPS operator*(const mint &v) const { return FPS(*this) *= v; } FPS operator/(const FPS &r) const { return FPS(*this) /= r; } FPS operator%(const FPS &r) const { return FPS(*this) %= r; } FPS operator-() const { FPS ret(this->size()); for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i]; return ret; } void shrink() { while (this->size() && this->back() == mint(0)) this->pop_back(); } FPS rev() const { FPS ret(*this); reverse(begin(ret), end(ret)); return ret; } FPS dot(FPS r) const { FPS ret(min(this->size(), r.size())); for (int i = 0; i < (int)ret.size(); i++) ret[i] = (*this)[i] * r[i]; return ret; } FPS pre(int sz) const { return FPS(begin(*this), begin(*this) + min((int)this->size(), sz)); } FPS operator>>(int sz) const { if ((int)this->size() <= sz) return {}; FPS ret(*this); ret.erase(ret.begin(), ret.begin() + sz); return ret; } FPS operator<<(int sz) const { FPS ret(*this); ret.insert(ret.begin(), sz, mint(0)); return ret; } FPS diff() const { const int n = (int)this->size(); FPS ret(max(0, n - 1)); mint one(1), coeff(1); for (int i = 1; i < n; i++) { ret[i - 1] = (*this)[i] * coeff; coeff += one; } return ret; } FPS integral() const { const int n = (int)this->size(); FPS ret(n + 1); ret[0] = mint(0); if (n > 0) ret[1] = mint(1); auto mod = mint::get_mod(); for (int i = 2; i <= n; i++) ret[i] = (-ret[mod % i]) * (mod / i); for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i]; return ret; } mint eval(mint x) const { mint r = 0, w = 1; for (auto &v : *this) r += w * v, w *= x; return r; } FPS log(int deg = -1) const { assert((*this)[0] == mint(1)); if (deg == -1) deg = (int)this->size(); return (this->diff() * this->inv(deg)).pre(deg - 1).integral(); } FPS pow(int64_t k, int deg = -1) const { const int n = (int)this->size(); if (deg == -1) deg = n; if (k == 0) { FPS ret(deg); if (deg) ret[0] = 1; return ret; } for (int i = 0; i < n; i++) { if ((*this)[i] != mint(0)) { mint rev = mint(1) / (*this)[i]; FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg); ret *= (*this)[i].pow(k); ret = (ret << (i * k)).pre(deg); if ((int)ret.size() < deg) ret.resize(deg, mint(0)); return ret; } if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0)); } return FPS(deg, mint(0)); } static void *ntt_ptr; static void set_fft(); FPS &operator*=(const FPS &r); void ntt(); void intt(); void ntt_doubling(); static int ntt_pr(); FPS inv(int deg = -1) const; FPS exp(int deg = -1) const; }; template <typename mint> void *FormalPowerSeries<mint>::ntt_ptr = nullptr; /** * @brief 多項式/形式的冪級数ライブラリ * @docs docs/fps/formal-power-series.md */ #line 5 "fps/ntt-friendly-fps.hpp" template <typename mint> void FormalPowerSeries<mint>::set_fft() { if (!ntt_ptr) ntt_ptr = new NTT<mint>; } template <typename mint> FormalPowerSeries<mint>& FormalPowerSeries<mint>::operator*=( const FormalPowerSeries<mint>& r) { if (this->empty() || r.empty()) { this->clear(); return *this; } set_fft(); auto ret = static_cast<NTT<mint>*>(ntt_ptr)->multiply(*this, r); return *this = FormalPowerSeries<mint>(ret.begin(), ret.end()); } template <typename mint> void FormalPowerSeries<mint>::ntt() { set_fft(); static_cast<NTT<mint>*>(ntt_ptr)->ntt(*this); } template <typename mint> void FormalPowerSeries<mint>::intt() { set_fft(); static_cast<NTT<mint>*>(ntt_ptr)->intt(*this); } template <typename mint> void FormalPowerSeries<mint>::ntt_doubling() { set_fft(); static_cast<NTT<mint>*>(ntt_ptr)->ntt_doubling(*this); } template <typename mint> int FormalPowerSeries<mint>::ntt_pr() { set_fft(); return static_cast<NTT<mint>*>(ntt_ptr)->pr; } template <typename mint> FormalPowerSeries<mint> FormalPowerSeries<mint>::inv(int deg) const { assert((*this)[0] != mint(0)); if (deg == -1) deg = (int)this->size(); FormalPowerSeries<mint> res(deg); res[0] = {mint(1) / (*this)[0]}; for (int d = 1; d < deg; d <<= 1) { FormalPowerSeries<mint> f(2 * d), g(2 * d); for (int j = 0; j < min((int)this->size(), 2 * d); j++) f[j] = (*this)[j]; for (int j = 0; j < d; j++) g[j] = res[j]; f.ntt(); g.ntt(); for (int j = 0; j < 2 * d; j++) f[j] *= g[j]; f.intt(); for (int j = 0; j < d; j++) f[j] = 0; f.ntt(); for (int j = 0; j < 2 * d; j++) f[j] *= g[j]; f.intt(); for (int j = d; j < min(2 * d, deg); j++) res[j] = -f[j]; } return res.pre(deg); } template <typename mint> FormalPowerSeries<mint> FormalPowerSeries<mint>::exp(int deg) const { using fps = FormalPowerSeries<mint>; assert((*this).size() == 0 || (*this)[0] == mint(0)); if (deg == -1) deg = this->size(); fps inv; inv.reserve(deg + 1); inv.push_back(mint(0)); inv.push_back(mint(1)); auto inplace_integral = [&](fps& F) -> void { const int n = (int)F.size(); auto mod = mint::get_mod(); while ((int)inv.size() <= n) { int i = inv.size(); inv.push_back((-inv[mod % i]) * (mod / i)); } F.insert(begin(F), mint(0)); for (int i = 1; i <= n; i++) F[i] *= inv[i]; }; auto inplace_diff = [](fps& F) -> void { if (F.empty()) return; F.erase(begin(F)); mint coeff = 1, one = 1; for (int i = 0; i < (int)F.size(); i++) { F[i] *= coeff; coeff += one; } }; fps b{1, 1 < (int)this->size() ? (*this)[1] : 0}, c{1}, z1, z2{1, 1}; for (int m = 2; m < deg; m *= 2) { auto y = b; y.resize(2 * m); y.ntt(); z1 = z2; fps z(m); for (int i = 0; i < m; ++i) z[i] = y[i] * z1[i]; z.intt(); fill(begin(z), begin(z) + m / 2, mint(0)); z.ntt(); for (int i = 0; i < m; ++i) z[i] *= -z1[i]; z.intt(); c.insert(end(c), begin(z) + m / 2, end(z)); z2 = c; z2.resize(2 * m); z2.ntt(); fps x(begin(*this), begin(*this) + min<int>(this->size(), m)); x.resize(m); inplace_diff(x); x.push_back(mint(0)); x.ntt(); for (int i = 0; i < m; ++i) x[i] *= y[i]; x.intt(); x -= b.diff(); x.resize(2 * m); for (int i = 0; i < m - 1; ++i) x[m + i] = x[i], x[i] = mint(0); x.ntt(); for (int i = 0; i < 2 * m; ++i) x[i] *= z2[i]; x.intt(); x.pop_back(); inplace_integral(x); for (int i = m; i < min<int>(this->size(), 2 * m); ++i) x[i] += (*this)[i]; fill(begin(x), begin(x) + m, mint(0)); x.ntt(); for (int i = 0; i < 2 * m; ++i) x[i] *= y[i]; x.intt(); b.insert(end(b), begin(x) + m, end(x)); } return fps{begin(b), begin(b) + deg}; } /** * @brief NTT mod用FPSライブラリ * @docs docs/fps/ntt-friendly-fps.md */ #line 2 "matrix/polynomial-matrix-prefix-prod.hpp" #line 2 "fps/sample-point-shift.hpp" #line 2 "modulo/binomial.hpp" template <typename T> struct Binomial { vector<T> f, g, h; Binomial(int MAX = 0) { assert(T::get_mod() != 0 && "Binomial<mint>()"); f.resize(1, T{1}); g.resize(1, T{1}); h.resize(1, T{1}); while (MAX >= (int)f.size()) extend(); } void extend() { int n = f.size(); int m = n * 2; f.resize(m); g.resize(m); h.resize(m); for (int i = n; i < m; i++) f[i] = f[i - 1] * T(i); g[m - 1] = f[m - 1].inverse(); h[m - 1] = g[m - 1] * f[m - 2]; for (int i = m - 2; i >= n; i--) { g[i] = g[i + 1] * T(i + 1); h[i] = g[i] * f[i - 1]; } } T fac(int i) { if (i < 0) return T(0); while (i >= (int)f.size()) extend(); return f[i]; } T finv(int i) { if (i < 0) return T(0); while (i >= (int)g.size()) extend(); return g[i]; } T inv(int i) { if (i < 0) return -inv(-i); while (i >= (int)h.size()) extend(); return h[i]; } T C(int n, int r) { if (n < 0 || n < r || r < 0) return T(0); return fac(n) * finv(n - r) * finv(r); } inline T operator()(int n, int r) { return C(n, r); } template <typename I> T multinomial(const vector<I>& r) { static_assert(is_integral<I>::value == true); int n = 0; for (auto& x : r) { if (x < 0) return T(0); n += x; } T res = fac(n); for (auto& x : r) res *= finv(x); return res; } template <typename I> T operator()(const vector<I>& r) { return multinomial(r); } T C_naive(int n, int r) { if (n < 0 || n < r || r < 0) return T(0); T ret = T(1); r = min(r, n - r); for (int i = 1; i <= r; ++i) ret *= inv(i) * (n--); return ret; } T P(int n, int r) { if (n < 0 || n < r || r < 0) return T(0); return fac(n) * finv(n - r); } T H(int n, int r) { if (n < 0 || r < 0) return T(0); return r == 0 ? 1 : C(n + r - 1, r); } }; #line 5 "fps/sample-point-shift.hpp" // input : y(0), y(1), ..., y(n - 1) // output : y(t), y(t + 1), ..., y(t + m - 1) // (if m is default, m = n) template <typename mint> FormalPowerSeries<mint> SamplePointShift(FormalPowerSeries<mint>& y, mint t, int m = -1) { if (m == -1) m = y.size(); long long T = t.get(); int k = (int)y.size() - 1; T %= mint::get_mod(); if (T <= k) { FormalPowerSeries<mint> ret(m); int ptr = 0; for (int64_t i = T; i <= k and ptr < m; i++) { ret[ptr++] = y[i]; } if (k + 1 < T + m) { auto suf = SamplePointShift<mint>(y, k + 1, m - ptr); for (int i = k + 1; i < T + m; i++) { ret[ptr++] = suf[i - (k + 1)]; } } return ret; } if (T + m > mint::get_mod()) { auto pref = SamplePointShift<mint>(y, T, mint::get_mod() - T); auto suf = SamplePointShift<mint>(y, 0, m - pref.size()); copy(begin(suf), end(suf), back_inserter(pref)); return pref; } FormalPowerSeries<mint> finv(k + 1, 1), d(k + 1); for (int i = 2; i <= k; i++) finv[k] *= i; finv[k] = mint(1) / finv[k]; for (int i = k; i >= 1; i--) finv[i - 1] = finv[i] * i; for (int i = 0; i <= k; i++) { d[i] = finv[i] * finv[k - i] * y[i]; if ((k - i) & 1) d[i] = -d[i]; } FormalPowerSeries<mint> h(m + k); for (int i = 0; i < m + k; i++) { h[i] = mint(1) / (T - k + i); } auto dh = d * h; FormalPowerSeries<mint> ret(m); mint cur = T; for (int i = 1; i <= k; i++) cur *= T - i; for (int i = 0; i < m; i++) { ret[i] = cur * dh[k + i]; cur *= T + i + 1; cur *= h[i]; } return ret; } #line 2 "matrix/matrix.hpp" template <class T> struct Matrix { vector<vector<T> > A; Matrix() = default; Matrix(int n, int m) : A(n, vector<T>(m, T())) {} Matrix(int n) : A(n, vector<T>(n, T())){}; int H() const { return A.size(); } int W() const { return A[0].size(); } int size() const { return A.size(); } inline const vector<T> &operator[](int k) const { return A[k]; } inline vector<T> &operator[](int k) { return A[k]; } static Matrix I(int n) { Matrix mat(n); for (int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix &operator+=(const Matrix &B) { int n = H(), m = W(); assert(n == B.H() && m == B.W()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B) { int n = H(), m = W(); assert(n == B.H() && m == B.W()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B) { int n = H(), m = B.W(), p = W(); assert(p == B.H()); vector<vector<T> > C(n, vector<T>(m, T{})); for (int i = 0; i < n; i++) for (int k = 0; k < p; k++) for (int j = 0; j < m; j++) C[i][j] += (*this)[i][k] * B[k][j]; A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::I(H()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } bool operator==(const Matrix &B) const { assert(H() == B.H() && W() == B.W()); for (int i = 0; i < H(); i++) for (int j = 0; j < W(); j++) if (A[i][j] != B[i][j]) return false; return true; } bool operator!=(const Matrix &B) const { assert(H() == B.H() && W() == B.W()); for (int i = 0; i < H(); i++) for (int j = 0; j < W(); j++) if (A[i][j] != B[i][j]) return true; return false; } friend ostream &operator<<(ostream &os, const Matrix &p) { int n = p.H(), m = p.W(); for (int i = 0; i < n; i++) { os << (i ? " " : "") << "["; for (int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() const { Matrix B(*this); assert(H() == W()); T ret = 1; for (int i = 0; i < H(); i++) { int idx = -1; for (int j = i; j < W(); j++) { if (B[j][i] != 0) { idx = j; break; } } if (idx == -1) return 0; if (i != idx) { ret *= T(-1); swap(B[i], B[idx]); } ret *= B[i][i]; T inv = T(1) / B[i][i]; for (int j = 0; j < W(); j++) { B[i][j] *= inv; } for (int j = i + 1; j < H(); j++) { T a = B[j][i]; if (a == 0) continue; for (int k = i; k < W(); k++) { B[j][k] -= B[i][k] * a; } } } return ret; } }; /** * @brief 行列ライブラリ */ #line 6 "matrix/polynomial-matrix-prefix-prod.hpp" // return m(k-1) * m(k-2) * ... * m(1) * m(0) template <typename mint> Matrix<mint> polynomial_matrix_prod(Matrix<FormalPowerSeries<mint>> &m, long long k) { using Mat = Matrix<mint>; using fps = FormalPowerSeries<mint>; auto shift = [](vector<Mat> &G, mint x) -> vector<Mat> { int d = G.size(), n = G[0].size(); vector<Mat> H(d, Mat(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { fps g(d); for (int l = 0; l < d; l++) g[l] = G[l][i][j]; fps h = SamplePointShift(g, x); for (int l = 0; l < d; l++) H[l][i][j] = h[l]; } } return H; }; int n = m.size(); int deg = 1; for (auto &_ : m.A) { for (auto &x : _) deg = max<int>(deg, (int)x.size() - 1); } while (deg & (deg - 1)) deg++; vector<Mat> G(deg + 1); long long v = 1; while (deg * v * v < k) v *= 2; mint iv = mint(v).inverse(); for (int i = 0; i < (int)G.size(); i++) { mint x = mint(v) * i; Mat mt(n); for (int j = 0; j < n; j++) for (int l = 0; l < n; l++) mt[j][l] = m[j][l].eval(x); G[i] = mt; } for (long long w = 1; w != v; w <<= 1) { mint W = w; auto G1 = shift(G, W * iv); auto G2 = shift(G, (W * deg * v + v) * iv); auto G3 = shift(G, (W * deg * v + v + W) * iv); for (int i = 0; i <= w * deg; i++) G[i] = G1[i] * G[i], G2[i] = G3[i] * G2[i]; copy(begin(G2), end(G2) - 1, back_inserter(G)); } Mat res = Mat::I(n); long long i = 0; while (i + v <= k) res = G[i / v] * res, i += v; while (i < k) { Mat mt(n); for (int j = 0; j < n; j++) for (int l = 0; l < n; l++) mt[j][l] = m[j][l].eval(i); res = mt * res; i++; } return res; } /** * @brief 多項式行列のprefix product */ #line 2 "misc/rng.hpp" namespace my_rand { using i64 = long long; using u64 = unsigned long long; // [0, 2^64 - 1) u64 rng() { static u64 _x = u64(chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count()) * 10150724397891781847ULL; _x ^= _x << 7; return _x ^= _x >> 9; } // [l, r] i64 rng(i64 l, i64 r) { assert(l <= r); return l + rng() % (r - l + 1); } // [l, r) i64 randint(i64 l, i64 r) { assert(l < r); return l + rng() % (r - l); } // choose n numbers from [l, r) without overlapping vector<i64> randset(i64 l, i64 r, i64 n) { assert(l <= r && n <= r - l); unordered_set<i64> s; for (i64 i = n; i; --i) { i64 m = randint(l, r + 1 - i); if (s.find(m) != s.end()) m = r - i; s.insert(m); } vector<i64> ret; for (auto& x : s) ret.push_back(x); return ret; } // [0.0, 1.0) double rnd() { return rng() * 5.42101086242752217004e-20; } template <typename T> void randshf(vector<T>& v) { int n = v.size(); for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]); } } // namespace my_rand using my_rand::randint; using my_rand::randset; using my_rand::randshf; using my_rand::rnd; using my_rand::rng; #line 2 "modint/montgomery-modint.hpp" template <uint32_t mod> struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t &b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } constexpr mint &operator+=(const mint &b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint &operator-=(const mint &b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint &operator*=(const mint &b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint &b) const { return mint(*this) += b; } constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } constexpr bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } constexpr mint inverse() const { return pow(mod - 2); } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { int64_t t; is >> t; b = LazyMontgomeryModInt<mod>(t); return (is); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static constexpr u32 get_mod() { return mod; } }; #line 9 "verify/verify-unit-test/polynomial-matrix-prod.test.cpp" // using namespace Nyaan; using mint = LazyMontgomeryModInt<998244353>; using fps = FormalPowerSeries<mint>; using fmat = Matrix<fps>; using mat = Matrix<mint>; mat eval(fmat& f, mint x) { mat m(f.H(), f.W()); rep(i, f.H()) rep(j, f.W()) m[i][j] = f[i][j].eval(x); return m; } void test() { int n = randint(1, 6); int d = randint(1, 11); // cerr << " n : " << n << " d : " << d << endl; fmat m(n); rep(i, n) rep(j, n) { fps f(d); each(x, f) x = rng(); m[i][j] = f; } mat prod = mat::I(n); rep(k, 1000) { // if(k % 200 == 0 and k) cerr << k << " finished." << endl; mat m2 = polynomial_matrix_prod(m, k); assert(prod == m2); prod = eval(m, k) * prod; } // cerr << "ok" << endl; } void Nyaan::solve() { test(); int a, b; cin >> a >> b; cout << a + b << endl; } } // nyaan Mint brute(Int n, Int k) { Mint ret = 0; Mint pw = 1; for (int a2 = 0; a2 <= k / 2; ++a2) { if (a2 >= k - n) { Mint num = 1; num *= fac[n] * invFac[n - (k - a2)] * invFac[k - 2 * a2] * invFac[a2]; num *= pw; ret += num; } pw *= inv[8]; } ret *= fac[k]; ret *= Mint(2).pow(k); return ret; } // (a, b] Mint fa(Int a, Int b) { using namespace nyaan; using fps = FormalPowerSeries<mint>; Matrix<fps> m(1); m[0][0] = fps{b, -1}; const auto prod = polynomial_matrix_prod(m, b - a); return Mint(prod[0][0].get()); } Mint solve(Int n, Int k) { if (k >= MO) { return 0; } const Int a0 = max(k - n, 0LL); const Int a1 = k / 2; assert(a0 <= a1); // n (n - 1) ... (n - (k - a1) + 1) if (n / MO != (n - (k - a1)) / MO) { return 0; } Mint f = fa((n - (k - a1)) % MO, n % MO); f /= fa(0, a1); f *= inv[8].pow(a1); /* ret = f; for (Int a = a1; a > a0; --a) { // a -> a-1 f = f * 8 * (n - k + a) * a / (k - 2 * a + 1) / (k - 2 * a + 2); ret += f; } */ { using namespace nyaan; using fps = FormalPowerSeries<mint>; Matrix<fps> m(2); m[0][0] = m[1][0] = fps{8} * fps{n - k + a1, -1} * fps{a1, -1}; m[1][1] = fps{k + 1 - 2 * a1, 2} * fps{k + 2 - 2 * a1, 2}; // cerr<<n<<" "<<k<<": m = "<<m<<endl; const auto prod = polynomial_matrix_prod(m, a1 - a0); f *= Mint((prod[1][0] + prod[1][1]).get()); } // /= (K - 2 a1 + 1) ... (K - 2 a0) f /= fa(k - 2 * a1, k - 2 * a0); f *= fa(0, k); f *= Mint(2).pow(k); return f; } int main() { for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) { Int N, K; scanf("%lld%lld", &N, &K); const Mint ans = solve(N, K); printf("%u\n", ans.x); } #ifndef LOCAL break; #endif } return 0; }