結果
問題 |
No.1907 DETERMINATION
|
ユーザー |
![]() |
提出日時 | 2025-08-19 23:13:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 782 ms / 4,000 ms |
コード長 | 60,367 bytes |
コンパイル時間 | 4,612 ms |
コンパイル使用メモリ | 333,284 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-19 23:14:06 |
合計ジャッジ時間 | 34,116 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 63 |
ソースコード
// // det(M1x + M0) の計算, for given N x N matrix M0, M1, in O(N^3) // // verified: // yukicoder No.1907 DETERMINATION // https://yukicoder.me/problems/no/1907 // #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; //------------------------------// // Utility //------------------------------// template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } using pint = pair<int, int>; using pll = pair<long long, long long>; using tint = array<int, 3>; using tll = array<long long, 3>; using fint = array<int, 4>; using fll = array<long long, 4>; using qint = array<int, 5>; using qll = array<long long, 5>; using vint = vector<int>; using vll = vector<long long>; using ll = long long; using u32 = unsigned int; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template <class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PB push_back #define MP make_pair #define MT make_tuple #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // debug stream template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, array<T, 3> P) { return s << '<' << P[0] << ", " << P[1] << ", " << P[2] << '>'; } template<class T> ostream& operator << (ostream &s, array<T, 4> P) { return s << '<' << P[0] << ", " << P[1] << ", " << P[2] << ", " << P[3] << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, deque<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template<class T> ostream& operator << (ostream &s, set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, multiset<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, unordered_set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, unordered_map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } // 4-neighbor const vector<int> dx = {1, 0, -1, 0}; const vector<int> dy = {0, 1, 0, -1}; // 8-neighbor const vector<int> dx8 = {1, 0, -1, 0, 1, -1, 1, -1}; const vector<int> dy8 = {0, 1, 0, -1, 1, 1, -1, -1}; // min non-negative i such that n <= 2^i int ceil_pow2(int n) { int i = 0; while ((1U << i) < (unsigned int)(n)) i++; return i; } // num of i such that (x & (1 << i)) != 0 int popcnt(int x) { return __builtin_popcount(x); } int popcnt(unsigned int x) { return __builtin_popcount(x); } int popcnt(long long x) { return __builtin_popcountll(x); } int popcnt(unsigned long long x) { return __builtin_popcountll(x); } // min non-negative i such that (x & (1 << i)) != 0 int bsf(int x) { return __builtin_ctz(x); } int bsf(unsigned int x) { return __builtin_ctz(x); } int bsf(long long x) { return __builtin_ctzll(x); } int bsf(unsigned long long x) { return __builtin_ctzll(x); } // max non-negative i such that (x & (1 << i)) != 0 int bsr(int x) { return 8 * (int)sizeof(int) - 1 - __builtin_clz(x); } int bsr(unsigned int x) { return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(x); } int bsr(long long x) { return 8 * (int)sizeof(long long) - 1 - __builtin_clzll(x); } int bsr(unsigned long long x) { return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(x); } // floor, ceil template<class T> T floor(T a, T b) { if (a % b == 0 || a >= 0) return a / b; else return -((-a) / b) - 1; } template<class T> T ceil(T x, T y) { return floor(x + y - 1, y); } // kth root // N < 2^64, K <= 64 uint64_t kth_root(uint64_t N, uint64_t K) { assert(K >= 1); if (N <= 1 || K == 1) return N; if (K >= 64) return 1; if (N == uint64_t(-1)) --N; auto mul = [&](uint64_t x, uint64_t y) -> uint64_t { if (x < UINT_MAX && y < UINT_MAX) return x * y; if (x == uint64_t(-1) || y == uint64_t(-1)) return uint64_t(-1); return (x <= uint64_t(-1) / y ? x * y : uint64_t(-1)); }; auto power = [&](uint64_t x, uint64_t k) -> uint64_t { if (k == 0) return 1ULL; uint64_t res = 1ULL; while (k) { if (k & 1) res = mul(res, x); x = mul(x, x); k >>= 1; } return res; }; uint64_t res; if (K == 2) res = sqrtl(N) - 1; else if (K == 3) res = cbrt(N) - 1; else res = pow(N, nextafter(1 / double(K), 0)); while (power(res + 1, K) <= N) ++res; return res; } // xor128による乱数生成、周期は2^128-1 unsigned int randInt() { static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123; unsigned int tt = (tx^(tx<<11)); tx = ty; ty = tz; tz = tw; return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) ); } int randInt(int minv, int maxv) { return randInt() % (maxv - minv + 1) + minv; } long long randInt(long long minv, long long maxv) { long long a = randInt(), b = randInt(); return (a * (1LL<<29) + b) % (maxv - minv + 1) + minv; } template<class T> void shuffle(vector<T>& vec) { int n = vec.size(); for (int i = n - 1; i > 0; --i) { int k = randInt() % (i + 1); swap(vec[i], vec[k]); } } // int 128 i128 to_integer(const string &s) { i128 res = 0; for (auto c : s) { if (isdigit(c)) res = res * 10 + (c - '0'); } if (s[0] == '-') res *= -1; return res; } istream& operator >> (istream &is, i128 &x) { string s; is >> s; x = to_integer(s); return is; } ostream& operator << (ostream &os, const i128 &x) { i128 ax = (x >= 0 ? x : -x); char buffer[128]; char *d = end(buffer); do { --d; *d = "0123456789"[ax % 10]; ax /= 10; } while (ax != 0); if (x < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); } return os; } // safe mod template<class T_VAL, class T_MOD> constexpr T_VAL safe_mod(T_VAL a, T_MOD m) { assert(m > 0); a %= m; if (a < 0) a += m; return a; } // mod pow template<class T_VAL, class T_MOD> constexpr T_VAL mod_pow(T_VAL a, T_VAL n, T_MOD m) { T_VAL res = 1; while (n > 0) { if (n % 2 == 1) res = res * a % m; a = a * a % m; n >>= 1; } return res; } // mod inv template<class T_VAL, class T_MOD> constexpr T_VAL mod_inv(T_VAL a, T_MOD m) { T_VAL b = m, u = 1, v = 0; while (b > 0) { T_VAL t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } u %= m; if (u < 0) u += m; return u; } // modint template<int MOD = 998244353, bool PRIME = true> struct Fp { // inner value unsigned int val; // constructor constexpr Fp() : val(0) { } template<std::signed_integral T> constexpr Fp(T v) { long long tmp = (long long)(v % (long long)(get_umod())); if (tmp < 0) tmp += get_umod(); val = (unsigned int)(tmp); } template<std::unsigned_integral T> constexpr Fp(T v) { val = (unsigned int)(v % get_umod()); } constexpr long long get() const { return val; } constexpr static int get_mod() { return MOD; } constexpr static unsigned int get_umod() { return MOD; } // arithmetic operators constexpr Fp operator + () const { return Fp(*this); } constexpr Fp operator - () const { return Fp() - Fp(*this); } constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; } constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; } constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; } constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp &r) { val += r.val; if (val >= get_umod()) val -= get_umod(); return *this; } constexpr Fp& operator -= (const Fp &r) { val -= r.val; if (val >= get_umod()) val += get_umod(); return *this; } constexpr Fp& operator *= (const Fp &r) { unsigned long long tmp = val; tmp *= r.val; val = (unsigned int)(tmp % get_umod()); return *this; } constexpr Fp& operator /= (const Fp &r) { return *this = *this * r.inv(); } constexpr Fp pow(long long n) const { assert(n >= 0); Fp res(1), mul(*this); while (n) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } constexpr Fp inv() const { if (PRIME) { assert(val); return pow(get_umod() - 2); } else { assert(val); return mod_inv((long long)(val), get_umod()); } } // other operators constexpr bool operator == (const Fp &r) const { return this->val == r.val; } constexpr bool operator != (const Fp &r) const { return this->val != r.val; } constexpr bool operator < (const Fp &r) const { return this->val < r.val; } constexpr bool operator > (const Fp &r) const { return this->val > r.val; } constexpr bool operator <= (const Fp &r) const { return this->val <= r.val; } constexpr bool operator >= (const Fp &r) const { return this->val >= r.val; } constexpr Fp& operator ++ () { ++val; if (val == get_umod()) val = 0; return *this; } constexpr Fp& operator -- () { if (val == 0) val = get_umod(); --val; return *this; } constexpr Fp operator ++ (int) { Fp res = *this; ++*this; return res; } constexpr Fp operator -- (int) { Fp res = *this; --*this; return res; } friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) { long long tmp = 1; is >> tmp; tmp = tmp % (long long)(get_umod()); if (tmp < 0) tmp += get_umod(); x.val = (unsigned int)(tmp); return is; } friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) { return os << x.val; } friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) { return r.pow(n); } friend constexpr Fp<MOD> inv(const Fp<MOD> &r) { return r.inv(); } }; // dynamic modint struct DynamicModint { using mint = DynamicModint; // static menber static int MOD; // inner value unsigned int val; // constructor DynamicModint() : val(0) { } template<std::signed_integral T> DynamicModint(T v) { long long tmp = (long long)(v % (long long)(get_umod())); if (tmp < 0) tmp += get_umod(); val = (unsigned int)(tmp); } template<std::unsigned_integral T> DynamicModint(T v) { val = (unsigned int)(v % get_umod()); } long long get() const { return val; } static int get_mod() { return MOD; } static unsigned int get_umod() { return MOD; } static void set_mod(int mod) { MOD = mod; } // arithmetic operators mint operator + () const { return mint(*this); } mint operator - () const { return mint() - mint(*this); } mint operator + (const mint &r) const { return mint(*this) += r; } mint operator - (const mint &r) const { return mint(*this) -= r; } mint operator * (const mint &r) const { return mint(*this) *= r; } mint operator / (const mint &r) const { return mint(*this) /= r; } mint& operator += (const mint &r) { val += r.val; if (val >= get_umod()) val -= get_umod(); return *this; } mint& operator -= (const mint &r) { val -= r.val; if (val >= get_umod()) val += get_umod(); return *this; } mint& operator *= (const mint &r) { unsigned long long tmp = val; tmp *= r.val; val = (unsigned int)(tmp % get_umod()); return *this; } mint& operator /= (const mint &r) { return *this = *this * r.inv(); } mint pow(long long n) const { assert(n >= 0); mint res(1), mul(*this); while (n) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } mint inv() const { assert(val); return mod_inv((long long)(val), get_umod()); } // other operators bool operator == (const mint &r) const { return this->val == r.val; } bool operator != (const mint &r) const { return this->val != r.val; } bool operator < (const mint &r) const { return this->val < r.val; } bool operator > (const mint &r) const { return this->val > r.val; } bool operator <= (const mint &r) const { return this->val <= r.val; } bool operator >= (const mint &r) const { return this->val >= r.val; } mint& operator ++ () { ++val; if (val == get_umod()) val = 0; return *this; } mint& operator -- () { if (val == 0) val = get_umod(); --val; return *this; } mint operator ++ (int) { mint res = *this; ++*this; return res; } mint operator -- (int) { mint res = *this; --*this; return res; } friend istream& operator >> (istream &is, mint &x) { long long tmp = 1; is >> tmp; tmp = tmp % (long long)(get_umod()); if (tmp < 0) tmp += get_umod(); x.val = (unsigned int)(tmp); return is; } friend ostream& operator << (ostream &os, const mint &x) { return os << x.val; } friend mint pow(const mint &r, long long n) { return r.pow(n); } friend mint inv(const mint &r) { return r.inv(); } }; int DynamicModint::MOD; // Binomial coefficient template<class mint> struct BiCoef { vector<mint> fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].get_mod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr mint com(int n, int k) const { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr mint fact(int n) const { if (n < 0) return 0; return fact_[n]; } constexpr mint inv(int n) const { if (n < 0) return 0; return inv_[n]; } constexpr mint finv(int n) const { if (n < 0) return 0; return finv_[n]; } }; // all inverse template<class mint> vector<mint> all_inverse(const vector<mint> &v) { for (auto &&vi : v) assert(vi != mint(0)); int N = (int)v.size(); vector<mint> res(N + 1, mint(1)); for (int i = 0; i < N; i++) res[i + 1] = res[i] * v[i]; mint t = res.back().inv(); res.pop_back(); for (int i = N - 1; i >= 0; i--) res[i] *= t, t *= v[i]; return res; } // calc primitive root constexpr int calc_primitive_root(long long m) { if (m == 1) return -1; if (m == 2) return 1; if (m == 998244353) return 3; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 645922817) return 3; if (m == 897581057) return 3; long long divs[20] = {}; divs[0] = 2; long long cnt = 1; long long x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (long long i = 3; i * i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } } if (x > 1) divs[cnt++] = x; for (long long g = 2; ; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (mod_pow(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } //------------------------------// // NTT //------------------------------// // NTT setup template<class mint, int MOD = mint::get_mod(), int g = calc_primitive_root(mint::get_mod())> struct ntt_setup { static constexpr int bsf_constexpr(unsigned int x) { int i = 0; while (!(x & (1 << i))) i++; return i; }; static constexpr int rank = bsf_constexpr(MOD - 1); array<mint, rank + 1> root, iroot; // root[i]^(2^i) = 1, root[i] * iroot[i] = 1 array<mint, max(0, rank - 1)> rate2, irate2; array<mint, max(0, rank - 2)> rate3, irate3; ntt_setup() { root[rank] = mint(g).pow((MOD - 1) >> rank); iroot[rank] = root[rank].inv(); for (int i = rank - 1; i >= 0; i--) { root[i] = root[i + 1] * root[i + 1]; iroot[i] = iroot[i + 1] * iroot[i + 1]; } mint prod = 1, iprod = 1; for (int i = 0; i < rank - 1; i++) { rate2[i] = root[i + 2] * prod; irate2[i] = iroot[i + 2] * iprod; prod *= iroot[i + 2]; iprod *= root[i + 2]; } prod = 1, iprod = 1; for (int i = 0; i < rank - 2; i++) { rate3[i] = root[i + 3] * prod; irate3[i] = iroot[i + 3] * iprod; prod *= iroot[i + 3]; iprod *= root[i + 3]; } } }; // NTT transformation template<class mint, int MOD = mint::get_mod()> void ntt_trans(vector<mint> &v) { int n = (int)v.size(); int h = ceil_pow2(n); static const ntt_setup<mint> setup; int len = 0; while (len < h) { if (h - len == 1) { int p = 1 << (h - len - 1); mint rot = 1; for (int s = 0; s < (1 << len); s++) { int offset = s << (h - len); for (int i = 0; i < p; i++) { auto l = v[i + offset]; auto r = v[i + offset + p] * rot; v[i + offset] = l + r; v[i + offset + p] = l - r; } if (s + 1 != (1 << len)) { rot *= setup.rate2[bsf(~(unsigned int)(s))]; } } len++; } else { int p = 1 << (h - len - 2); mint rot = 1, imag = setup.root[2]; for (int s = 0; s < (1 << len); s++) { mint rot2 = rot * rot, rot3 = rot2 * rot; int offset = s << (h - len); for (int i = 0; i < p; i++) { auto mod2 = 1ULL * MOD * MOD; auto a0 = 1ULL * v[i + offset].val; auto a1 = 1ULL * v[i + offset + p].val * rot.val; auto a2 = 1ULL * v[i + offset + p * 2].val * rot2.val; auto a3 = 1ULL * v[i + offset + p * 3].val * rot3.val; auto tmp = 1ULL * mint(a1 + mod2 - a3).val * imag.val; auto na2 = mod2 - a2; v[i + offset] = a0 + a2 + a1 + a3; v[i + offset + p] = a0 + a2 + (mod2 * 2 - (a1 + a3)); v[i + offset + p * 2] = a0 + na2 + tmp; v[i + offset + p * 3] = a0 + na2 + (mod2 - tmp); } if (s + 1 != (1 << len)) { rot *= setup.rate3[bsf(~(unsigned int)(s))]; } } len += 2; } } } // NTT inv-transformation template<class mint, int MOD = mint::get_mod()> void ntt_trans_inv(vector<mint> &v) { int n = (int)v.size(); int h = ceil_pow2(n); static const ntt_setup<mint> setup; int len = h; while (len) { if (len == 1) { int p = 1 << (h - len); mint irot = 1; for (int s = 0; s < (1 << (len - 1)); s++) { int offset = s << (h - len + 1); for (int i = 0; i < p; i++) { auto l = v[i + offset]; auto r = v[i + offset + p]; v[i + offset] = l + r; v[i + offset + p] = (unsigned long long)((long long)(MOD) + l.val - r.val) * irot.val; } if (s + 1 != (1 << (len - 1))) { irot *= setup.irate2[bsf(~(unsigned int)(s))]; } } len--; } else { int p = 1 << (h - len); mint irot = 1, iimag = setup.iroot[2]; for (int s = 0; s < (1 << (len - 2)); s++) { mint irot2 = irot * irot, irot3 = irot2 * irot; int offset = s << (h - len + 2); for (int i = 0; i < p; i++) { auto a0 = 1ULL * v[i + offset].val; auto a1 = 1ULL * v[i + offset + p].val; auto a2 = 1ULL * v[i + offset + p * 2].val; auto a3 = 1ULL * v[i + offset + p * 3].val; auto tmp = 1ULL * mint((MOD + a2 - a3) * iimag.val).val; v[i + offset] = a0 + a1 + a2 + a3; v[i + offset + p] = (a0 + (MOD - a1) + tmp) * irot.val; v[i + offset + p * 2] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val; v[i + offset + p * 3] = (a0 + (MOD - a1) + (MOD - tmp)) * irot3.val; } if (s + 1 != (1 << (len - 2))) { irot *= setup.irate3[bsf(~(unsigned int)(s))]; } } len -= 2; } } mint in = mint(n).inv(); for (int i = 0; i < n; i++) v[i] *= in; } // naive convolution template<class T> vector<T> sub_convolution_naive(const vector<T> &a, const vector<T> &b) { int n = (int)a.size(), m = (int)b.size(); vector<T> res(n + m - 1); if (n < m) { for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) res[i + j] += a[i] * b[j]; } else { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) res[i + j] += a[i] * b[j]; } return res; } // ntt convolution template<class mint> vector<mint> sub_convolution_ntt(vector<mint> a, vector<mint> b) { int MOD = mint::get_mod(); int n = (int)a.size(), m = (int)b.size(); if (!n || !m) return {}; int z = (int)bit_ceil((unsigned int)(n + m - 1)); assert((MOD - 1) % z == 0); a.resize(z), b.resize(z); ntt_trans(a), ntt_trans(b); for (int i = 0; i < z; i++) a[i] *= b[i]; ntt_trans_inv(a); a.resize(n + m - 1); return a; } // convolution in general mod template<class mint> vector<mint> convolution(const vector<mint> &a, const vector<mint> &b) { int n = (int)a.size(), m = (int)b.size(); if (!n || !m) return {}; if (min(n, m) <= 60) return sub_convolution_naive(std::move(a), std::move(b)); if constexpr (std::is_same_v<mint, Fp<998244353>>) return sub_convolution_ntt(a, b); static constexpr int MOD0 = 754974721; // 2^24 static constexpr int MOD1 = 167772161; // 2^25 static constexpr int MOD2 = 469762049; // 2^26 using mint0 = Fp<MOD0>; using mint1 = Fp<MOD1>; using mint2 = Fp<MOD2>; static const mint1 imod0 = 95869806; // modinv(MOD0, MOD1); static const mint2 imod1 = 104391568; // modinv(MOD1, MOD2); static const mint2 imod01 = 187290749; // imod1 / MOD0; vector<mint0> a0(n, 0), b0(m, 0); vector<mint1> a1(n, 0), b1(m, 0); vector<mint2> a2(n, 0), b2(m, 0); for (int i = 0; i < n; ++i) a0[i] = a[i].val, a1[i] = a[i].val, a2[i] = a[i].val; for (int i = 0; i < m; ++i) b0[i] = b[i].val, b1[i] = b[i].val, b2[i] = b[i].val; auto c0 = sub_convolution_ntt(std::move(a0), std::move(b0)); auto c1 = sub_convolution_ntt(std::move(a1), std::move(b1)); auto c2 = sub_convolution_ntt(std::move(a2), std::move(b2)); vector<mint> res(n + m - 1); mint mod0 = MOD0, mod01 = mod0 * MOD1; for (int i = 0; i < n + m - 1; ++i) { unsigned int y0 = c0[i].val; unsigned int y1 = (imod0 * (c1[i] - y0)).val; unsigned int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val; res[i] = mod01 * y2 + mod0 * y1 + y0; } return res; } //------------------------------// // FPS //------------------------------// // Formal Power Series template<class mint> struct FPS : vector<mint> { static const int SPARSE_BOARDER = 60; using vector<mint>::vector; // constructor constexpr FPS(const vector<mint> &r) : vector<mint>(r) {} // core operator constexpr FPS pre(int siz) const { return FPS(begin(*this), begin(*this) + min((int)this->size(), siz)); } constexpr FPS rev() const { FPS res = *this; reverse(begin(res), end(res)); return res; } constexpr FPS& normalize() { while (!this->empty() && this->back() == 0) this->pop_back(); return *this; } constexpr mint eval(const mint &v) const { mint res = 0; for (int i = (int)this->size()-1; i >= 0; --i) { res *= v; res += (*this)[i]; } return res; } constexpr int count_terms() const { int res = 0; for (int i = 0; i < (int)this->size(); i++) if ((*this)[i] != mint(0)) res++; return res; } // basic operator constexpr FPS operator - () const noexcept { FPS res = (*this); for (int i = 0; i < (int)res.size(); ++i) res[i] = -res[i]; return res; } constexpr FPS operator + (const mint &v) const { return FPS(*this) += v; } constexpr FPS operator + (const FPS &r) const { return FPS(*this) += r; } constexpr FPS operator - (const mint &v) const { return FPS(*this) -= v; } constexpr FPS operator - (const FPS &r) const { return FPS(*this) -= r; } constexpr FPS operator * (const mint &v) const { return FPS(*this) *= v; } constexpr FPS operator * (const FPS &r) const { return FPS(*this) *= r; } constexpr FPS operator / (const mint &v) const { return FPS(*this) /= v; } constexpr FPS operator / (const FPS &r) const { return FPS(*this) /= r; } constexpr FPS operator % (const FPS &r) const { return FPS(*this) %= r; } constexpr FPS operator << (int x) const { return FPS(*this) <<= x; } constexpr FPS operator >> (int x) const { return FPS(*this) >>= x; } constexpr FPS& operator += (const mint &v) { if (this->empty()) this->reserve(1), this->resize(1); (*this)[0] += v; return *this; } constexpr FPS& operator += (const FPS &r) { if (r.size() > this->size()) this->reserve(r.size()), this->resize(r.size()); for (int i = 0; i < (int)r.size(); ++i) (*this)[i] += r[i]; return this->normalize(); } constexpr FPS& operator -= (const mint &v) { if (this->empty()) this->reserve(1), this->resize(1); (*this)[0] -= v; return *this; } constexpr FPS& operator -= (const FPS &r) { if (r.size() > this->size()) this->reserve(r.size()), this->resize(r.size()); for (int i = 0; i < (int)r.size(); ++i) (*this)[i] -= r[i]; return this->normalize(); } constexpr FPS& operator *= (const mint &v) { for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= v; return *this; } constexpr FPS& operator *= (const FPS &r) { return *this = convolution((*this), r); } constexpr FPS& operator /= (const mint &v) { assert(v != 0); mint iv = v.inv(); for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= iv; return *this; } // division, r must be normalized (r.back() must not be 0) constexpr FPS& operator /= (const FPS &r) { assert(!r.empty()); assert(r.back() != 0); this->normalize(); if (this->size() < r.size()) { this->clear(); return *this; } int need = (int)this->size() - (int)r.size() + 1; *this = (rev().pre(need) * r.rev().inv(need)).pre(need).rev(); return *this; } constexpr FPS& operator %= (const FPS &r) { assert(!r.empty()); assert(r.back() != 0); this->normalize(); FPS q = (*this) / r; return *this -= q * r; } constexpr FPS& operator <<= (int x) { FPS res(x, 0); res.insert(res.end(), begin(*this), end(*this)); return *this = res; } constexpr FPS& operator >>= (int x) { FPS res; res.insert(res.end(), begin(*this) + x, end(*this)); return *this = res; } // advanced operation // df/dx constexpr FPS diff() const { int n = (int)this->size(); if (n <= 0) return FPS(); FPS res(n-1); for (int i = 1; i < n; ++i) res[i-1] = (*this)[i] * i; return res; } // \int f dx constexpr FPS integral() const { int n = (int)this->size(); FPS res(n+1, 0); for (int i = 0; i < n; ++i) res[i+1] = (*this)[i] / (i+1); return res; } // inv(f), f[0] must not be 0 constexpr FPS inv(int deg = -1) const { if (count_terms() <= SPARSE_BOARDER) return inv_sparse(deg); if constexpr (std::is_same_v<mint, Fp<998244353>>) return inv_ntt_friendly(deg); assert(this->size() >= 1 && (*this)[0] != 0); if (deg < 0) deg = (int)this->size(); FPS res({mint(1) / (*this)[0]}); for (int d = 1; d < deg; d <<= 1) { res = (res + res - res * res * pre(d << 1)).pre(d << 1); } res.resize(deg); return res; } constexpr FPS inv_ntt_friendly(int deg = -1) const { assert(this->size() >= 1 && (*this)[0] != 0); if (deg < 0) deg = (int)this->size(); FPS res(deg); res[0] = mint(1) / (*this)[0]; for (int d = 1; d < deg; d <<= 1) { FPS g(d * 2), h(d * 2); mint iv = mint(d * 2).inv(); for (int i = 0; i < min((int)this->size(), d * 2); i++) g[i] = (*this)[i]; for (int i = 0; i < d; i++) h[i] = res[i]; ntt_trans(g), ntt_trans(h); for (int i = 0; i < d * 2; i++) g[i] *= h[i]; ntt_trans_inv(g); for (int i = 0; i < d; i++) g[i] = 0; ntt_trans(g); for (int i = 0; i < d * 2; i++) g[i] *= h[i]; ntt_trans_inv(g); for (int i = d; i < min(deg, d * 2); i++) res[i] = -g[i]; } return res.pre(deg); } constexpr FPS inv_sparse(int deg = -1) const { assert(this->size() >= 1 && (*this)[0] != 0); if (deg < 0) deg = (int)this->size(); vector<pair<int, mint>> dat; for (int i = 1; i < (int)this->size(); i++) if ((*this)[i] != mint(0)) { dat.emplace_back(i, (*this)[i]); } vector<mint> res(deg); res[0] = (*this)[0].inv(); for (int i = 1; i < deg; i++) { mint r = 0; for (auto &&[k, val] : dat) { if (k > i) break; r -= val * res[i - k]; } res[i] = r * res[0]; } return res; } // log(f) = \int f'/f dx, f[0] must be 1 constexpr FPS log(int deg = -1) const { assert(this->size() >= 1 && (*this)[0] == 1); if (count_terms() <= SPARSE_BOARDER) return log_sparse(deg); if (deg < 0) deg = (int)this->size(); return ((diff() * inv(deg)).pre(deg - 1)).integral(); } constexpr FPS log_sparse(int deg = -1) const { assert(this->size() >= 1 && (*this)[0] == 1); if (deg < 0) deg = (int)this->size(); vector<pair<int, mint>> dat; for (int i = 1; i < (int)this->size(); i++) if ((*this)[i] != mint(0)) { dat.emplace_back(i, (*this)[i]); } BiCoef<mint> bc(deg); vector<mint> res(deg), tmp(deg); for (int i = 0; i < deg - 1; i++) { mint r = mint(i + 1) * (*this)[i + 1]; for (auto &&[k, val] : dat) { if (k > i) break; r -= val * tmp[i - k]; } tmp[i] = r; res[i + 1] = r * bc.inv(i + 1); } return res; } // exp(f), f[0] must be 0 constexpr FPS exp(int deg = -1) const { if ((int)this->size() == 0) return {mint(1)}; if (count_terms() <= SPARSE_BOARDER) return exp_sparse(deg); if constexpr (std::is_same_v<mint, Fp<998244353>>) return exp_ntt_friendly(deg); assert((*this)[0] == 0); if (deg < 0) deg = (int)this->size(); FPS res(1, 1); for (int d = 1; d < deg; d <<= 1) { res = res * (pre(d << 1) - res.log(d << 1) + 1).pre(d << 1); } res.resize(deg); return res; } constexpr FPS exp_ntt_friendly(int deg = -1) const { if ((int)this->size() == 0) return {mint(1)}; assert((*this)[0] == 0); if (deg < 0) deg = (int)this->size(); FPS fiv; fiv.reserve(deg + 1); fiv.emplace_back(mint(0)); fiv.emplace_back(mint(1)); auto inplace_integral = [&](FPS &F) -> void { const int n = (int)F.size(); auto mod = mint::get_mod(); while ((int)fiv.size() <= n) { int i = fiv.size(); fiv.emplace_back((-fiv[mod % i]) * (mod / i)); } F.insert(begin(F), mint(0)); for (int i = 1; i <= n; i++) F[i] *= fiv[i]; }; auto inplace_diff = [](FPS &F) -> void { if (F.empty()) return; F.erase(begin(F)); mint coef = 1; for (int i = 0; i < (int)F.size(); i++) { F[i] *= coef; coef++; } }; FPS b{1, (1 < (int)this->size() ? (*this)[1] : 0)}, c{1}, z1, z2{1, 1}; for (int m = 2; m < deg; m <<= 1) { auto y = b; y.resize(m * 2); ntt_trans(y); z1 = z2; FPS z(m); for (int i = 0; i < m; i++) z[i] = y[i] * z1[i]; ntt_trans_inv(z); fill(begin(z), begin(z) + m / 2, mint(0)); ntt_trans(z); for (int i = 0; i < m; i++) z[i] *= -z1[i]; ntt_trans_inv(z); c.insert(end(c), begin(z) + m / 2, end(z)); z2 = c; z2.resize(m * 2); ntt_trans(z2); FPS x(begin(*this), begin(*this) + min((int)this->size(), m)); inplace_diff(x); x.emplace_back(mint(0)); ntt_trans(x); for (int i = 0; i < m; i++) x[i] *= y[i]; ntt_trans_inv(x); x -= b.diff(); x.resize(m * 2); for (int i = 0; i < m - 1; i++) x[m + i] = x[i], x[i] = mint(0); ntt_trans(x); for (int i = 0; i < m * 2; i++) x[i] *= z2[i]; ntt_trans_inv(x); x.pop_back(); inplace_integral(x); for (int i = m; i < min((int)this->size(), m * 2); i++) x[i] += (*this)[i]; fill(begin(x), begin(x) + m, mint(0)); ntt_trans(x); for (int i = 0; i < m * 2; i++) x[i] *= y[i]; ntt_trans_inv(x); b.insert(end(b), begin(x) + m, end(x)); } return FPS(begin(b), begin(b) + deg); } constexpr FPS exp_sparse(int deg = -1) const { if ((int)this->size() == 0) return {mint(1)}; assert((*this)[0] == 0); if (deg < 0) deg = (int)this->size(); vector<pair<int, mint>> dat; for (int i = 1; i < (int)this->size(); i++) if ((*this)[i] != mint(0)) { dat.emplace_back(i - 1, (*this)[i] * i); } BiCoef<mint> bc(deg); vector<mint> res(deg); res[0] = 1; for (int i = 1; i < deg; i++) { mint r = 0; for (auto &&[k, val] : dat) { if (k > i - 1) break; r += val * res[i - k - 1]; } res[i] = r * bc.inv(i); } return res; } // pow(f) = exp(e * log f) constexpr FPS pow(long long e, int deg = -1) const { if (count_terms() <= SPARSE_BOARDER) return pow_sparse(e, deg); assert(e >= 0); if (deg < 0) deg = (int)this->size(); if (deg == 0) return FPS(); if (e == 0) { FPS res(deg, 0); res[0] = 1; return res; } long long ord = 0; while (ord < (int)this->size() && (*this)[ord] == 0) ord++; if (ord == (int)this->size() || ord > (deg - 1) / e) return FPS(deg, 0); mint k = (*this)[ord]; FPS res = ((((*this) >> ord) / k).log(deg) * e).exp(deg) * mint(k).pow(e) << (e * ord); res.resize(deg); return res; } constexpr FPS pow_sparse(long long e, int deg = -1) const { assert(e >= 0); if (deg < 0) deg = (int)this->size(); if (deg == 0) return FPS(); if (e == 0) { FPS res(deg, 0); res[0] = 1; return res; } long long ord = 0; while (ord < (int)this->size() && (*this)[ord] == 0) ord++; if (ord == (int)this->size() || ord > (deg - 1) / e) return FPS(deg, 0); if ((*this)[0] == 1) return pow_sparse_constant1(e, deg); auto f = (*this); rotate(f.begin(), f.begin() + ord, f.end()); mint con = f[0], icon = f[0].inv(); for (int i = 0; i < deg; i++) f[i] *= icon; auto res = f.pow_sparse_constant1(e, deg); int ord2 = e * ord; rotate(res.begin(), res.begin() + (deg - ord2), res.end()); fill(res.begin(), res.begin() + ord2, mint(0)); mint pw = con.pow(e); for (int i = ord2; i < deg; i++) res[i] *= pw; return res; } constexpr FPS pow_sparse_constant1(mint e, int deg = -1) const { assert((int)this->size() > 0 && (*this)[0] == 1); if (deg < 0) deg = (int)this->size(); vector<pair<int, mint>> dat; for (int i = 1; i < (int)this->size(); i++) if ((*this)[i] != mint(0)) { dat.emplace_back(i, (*this)[i]); } BiCoef<mint> bc(deg); vector<mint> res(deg); res[0] = 1; for (int i = 0; i < deg - 1; i++) { mint &r = res[i + 1]; for (auto &&[k, val] : dat) { if (k > i + 1) break; mint t = val * res[i - k + 1]; r += t * (mint(k) * e - mint(i - k + 1)); } r *= bc.inv(i + 1); } return res; } // sqrt(f) constexpr FPS sqrt(int deg = -1) const { if (count_terms() <= SPARSE_BOARDER) return sqrt_sparse(deg); if (deg < 0) deg = (int)this->size(); if ((int)this->size() == 0) return FPS(deg, 0); if ((*this)[0] == mint(0)) { for (int i = 1; i < (int)this->size(); i++) { if ((*this)[i] != mint(0)) { if (i & 1) return FPS(); if (deg - i / 2 <= 0) return FPS(deg, 0); auto res = ((*this) >> i).sqrt(deg - i / 2); if (res.empty()) return FPS(); res = res << (i / 2); if ((int)res.size() < deg) res.resize(deg, mint(0)); return res; } } return FPS(deg, 0); } long long sqr = mod_sqrt<long long>((*this)[0].val, mint::get_mod()); if (sqr == -1) return FPS(); assert((*this)[0].val == sqr * sqr % mint::get_mod()); FPS res = {mint(sqr)}; mint iv2 = mint(2).inv(); for (int d = 1; d < deg; d <<= 1) { res = (res + pre(d << 1) * res.inv(d << 1)).pre(d << 1) * iv2; } res.resize(deg); return res; } constexpr FPS sqrt_sparse(int deg) const { if (deg < 0) deg = (int)this->size(); if ((int)this->size() == 0) return FPS(deg, 0); if ((*this)[0] == mint(0)) { for (int i = 1; i < (int)this->size(); i++) { if ((*this)[i] != mint(0)) { if (i & 1) return FPS(); if (deg - i / 2 <= 0) return FPS(deg, 0); auto res = ((*this) >> i).sqrt_sparse(deg - i / 2); if (res.empty()) return FPS(); res = res << (i / 2); if ((int)res.size() < deg) res.resize(deg, mint(0)); return res; } } return FPS(deg, 0); } mint con = (*this)[0], icon = con.inv(); long long sqr = mod_sqrt<long long>(con.val, mint::get_mod()); if (sqr == -1) return FPS(); assert(con.val == sqr * sqr % mint::get_mod()); auto res = (*this) * icon; return res.sqrt_sparse_constant1(deg) * sqr; } constexpr FPS sqrt_sparse_constant1(int deg) const { return pow_sparse_constant1(mint(2).inv(), deg); } // friend operators friend constexpr FPS diff(const FPS &f) { return f.diff(); } friend constexpr FPS integral(const FPS &f) { return f.integral(); } friend constexpr FPS inv(const FPS &f, int deg = -1) { return f.inv(deg); } friend constexpr FPS log(const FPS &f, int deg = -1) { return f.log(deg); } friend constexpr FPS exp(const FPS &f, int deg = -1) { return f.exp(deg); } friend constexpr FPS pow(const FPS &f, long long e, int deg = -1) { return f.pow(e, deg); } friend constexpr FPS sqrt(const FPS &f, int deg = -1) { return f.sqrt(deg); } }; //------------------------------// // Polynomial Algorithms //------------------------------// // find f(x)^n mod g(x) template<class mint, class T_VAL = long long> FPS<mint> mod_pow(const FPS<mint> &f, T_VAL e, const FPS<mint> &mod) { assert(!mod.empty()); auto iv = mod.rev().inv(); auto calc_quo = [&](const FPS<mint> &pol) -> FPS<mint> { if (pol.size() < mod.size()) return FPS<mint>(); int deg = (int)pol.size() - (int)mod.size() + 1; return (pol.rev().pre(deg) * iv.pre(deg)).pre(deg).rev(); }; FPS<mint> res{1}, b(f); while (e) { if (e & 1) res *= b, res -= calc_quo(res) * mod; b *= b; b -= calc_quo(b) * mod; e >>= 1; assert(b.size() + 1 <= mod.size()); assert(res.size() + 1 <= mod.size()); } return res; } // middle product // c[i] = sum_j a[i+j]b[j] (deg(a) = n, deg(b) = m -> deg(c) = n-m) template<class mint> FPS<mint> middle_product(const FPS<mint> &a, const FPS<mint> &b) { assert(a.size() >= b.size()); if (b.empty()) return FPS<mint>((int)a.size() - (int)b.size() + 1); int N = 1; while (N < (int)a.size()) N <<= 1; FPS<mint> fa(N), fb(N); copy(a.begin(), a.end(), fa.begin()); copy(b.rbegin(), b.rend(), fb.begin()); fa *= fb; fa.resize(a.size()); fa.erase(fa.begin(), fa.begin() + (int)b.size() - 1); return fa; } // multipoint evaluation, polynomial interpolation template<class mint> struct SubproductTree { // inner data int num_points, siz; vector<FPS<mint>> tree; // constructor SubproductTree() {} SubproductTree(const vector<mint> &x) { num_points = (int)x.size(); siz = 1; while (siz < num_points) siz <<= 1; tree.resize(siz * 2); for (int i = 0; i < siz; i++) tree[siz + i] = {1, (i < num_points ? -x[i] : 0)}; for (int i = siz - 1; i >= 1; i--) tree[i] = tree[i * 2] * tree[i * 2 + 1]; } // multipoint evaluation vector<mint> eval(FPS<mint> f) { int N = (int)f.size(); if (N == 0) return vector<mint>(num_points, mint(0)); f.resize(N * 2 - 1); vector<FPS<mint>> g(siz * 2); g[1] = tree[1]; g[1].resize(N); g[1] = inv(g[1]); g[1] = middle_product(f, g[1]); g[1].resize(siz); for (int i = 1; i < siz; i++) { g[i * 2] = middle_product(g[i], tree[i * 2 + 1]); g[i * 2 + 1] = middle_product(g[i], tree[i * 2]); } vector<mint> res(num_points); for (int i = 0; i < num_points; i++) res[i] = g[siz + i][0]; return res; } // polynomial interpolation FPS<mint> interpolate(const vector<mint> &y) { assert((int)y.size() == num_points); vector<mint> p(num_points); for (int i = 0; i < num_points; i++) p[i] = tree[1][num_points - i - 1] * (i + 1); p = eval(p); vector<FPS<mint>> t(siz * 2); for (int i = 0; i < siz; i++) t[siz + i] = {(i < num_points ? y[i] / p[i] : 0)}; for (int i = siz - 1; i >= 1; i--) { t[i] = t[i * 2] * tree[i * 2 + 1]; auto rt = t[i * 2 + 1] * tree[i * 2]; for (int k = 0; k < (int)t[i].size(); k++) t[i][k] += rt[k]; } t[1].resize(num_points); reverse(t[1].begin(), t[1].end()); return t[1]; } }; // multipoint evaluation, polynomial interpolation template<class mint> vector<mint> multipoint_eval(const FPS<mint> &f, const vector<mint> &x) { if (x.empty()) return {}; SubproductTree<mint> st(x); return st.eval(f); } template<class mint> FPS<mint> interpolate(const vector<mint> &x, const vector<mint> &y) { assert(x.size() == y.size()); if (x.empty()) return {}; SubproductTree<mint> st(x); return st.interpolate(y); } // polynomial interpolation (case: geometric sequence) // y[i] = f(ar^i) -> find f template<class mint> vector<mint> interpolate(const mint &a, const mint &r, const FPS<mint> &y) { int N = (int)y.size(); if (N == 0) return FPS<mint>(); if (N == 1) return {y[0]}; auto Y = y; mint ir = r.inv(), ia = a.inv(); FPS<mint> po(N + N - 1, 1), po2(N + N - 1, 1), ipo(N + N - 1, 1), ipo2(N + N - 1, 1); for (int i = 0; i < N + N - 2; i++) po[i + 1] = po[i] * r, po2[i + 1] = po2[i] * po[i]; for (int i = 0; i < N; i++) ipo[i + 1] = ipo[i] * ir, ipo2[i + 1] = ipo2[i] * ipo[i]; vector<mint> S(N, mint(1)); for (int i = 1; i < N; i++) S[i] = S[i - 1] * (mint(1) - po[i]); vector<mint> iS = all_inverse(S); mint sn = S[N - 1] * (mint(1) - po[N]); for (int i = 0; i < N; i++) { Y[i] = Y[i] * po2[N - i - 1] * ipo2[N - 1] * iS[i] * iS[N - i - 1]; if (i & 1) Y[i] = -Y[i]; } for (int i = 0; i < N; i++) Y[i] *= ipo2[i]; FPS<mint> f = middle_product(po2, Y); for (int i = 0; i < N; i++) f[i] *= ipo2[i]; FPS<mint> g(N, mint(1)); for (int i = 1; i < N; i++) { g[i] = po2[i] * sn * iS[i] * iS[N - i]; if (i & 1) g[i] = -g[i]; } f = f * g; f.resize(N); reverse(f.begin(), f.end()); mint p = 1; for (int i = 0; i < N; i++) f[i] *= p, p *= ia; return f; } //------------------------------// // Matrix //------------------------------// // matrix template<class mint> struct MintMatrix { // inner value vector<vector<mint>> val; // constructors MintMatrix(int H, int W) : val(H, vector<mint>(W)) {} MintMatrix(int H, int W, mint x) : val(H, vector<mint>(W, x)) {} MintMatrix(const MintMatrix &mat) : val(mat.val) {} void init(int H, int W, mint x) { val.assign(H, vector<mint>(W, x)); } void resize(int H, int W) { val.resize(H); for (int i = 0; i < H; ++i) val[i].resize(W); } // getter and debugger constexpr int height() const { return (int)val.size(); } constexpr int width() const { return (height() > 0 ? (int)val[0].size() : 0); } vector<mint>& operator [] (int i) { return val[i]; } constexpr vector<mint>& operator [] (int i) const { return val[i]; } friend constexpr ostream& operator << (ostream &os, const MintMatrix<mint> &mat) { os << endl; for (int i = 0; i < mat.height(); ++i) { for (int j = 0; j < mat.width(); ++j) { if (j) os << ", "; os << mat.val[i][j]; } os << endl; } return os; } // comparison operators constexpr bool operator == (const MintMatrix &r) const { return this->val == r.val; } constexpr bool operator != (const MintMatrix &r) const { return this->val != r.val; } // arithmetic operators constexpr MintMatrix& operator += (const MintMatrix &r) { assert(height() == r.height()); assert(width() == r.width()); for (int i = 0; i < height(); ++i) { for (int j = 0; j < width(); ++j) { val[i][j] = val[i][j] + r.val[i][j]; } } return *this; } constexpr MintMatrix& operator -= (const MintMatrix &r) { assert(height() == r.height()); assert(width() == r.width()); for (int i = 0; i < height(); ++i) { for (int j = 0; j < width(); ++j) { val[i][j] = val[i][j] - r.val[i][j]; } } return *this; } constexpr MintMatrix& operator *= (const mint &v) { for (int i = 0; i < height(); ++i) for (int j = 0; j < width(); ++j) val[i][j] = val[i][j] * v; return *this; } constexpr MintMatrix& operator *= (const MintMatrix &r) { assert(width() == r.height()); MintMatrix<mint> res(height(), r.width()); for (int i = 0; i < height(); ++i) for (int j = 0; j < r.width(); ++j) for (int k = 0; k < width(); ++k) res[i][j] = res[i][j] + val[i][k] * r.val[k][j]; return (*this) = res; } constexpr MintMatrix operator + () const { return MintMatrix(*this); } constexpr MintMatrix operator - () const { return MintMatrix(*this) *= mint(-1); } constexpr MintMatrix operator + (const MintMatrix &r) const { return MintMatrix(*this) += r; } constexpr MintMatrix operator - (const MintMatrix &r) const { return MintMatrix(*this) -= r; } constexpr MintMatrix operator * (const mint &v) const { return MintMatrix(*this) *= v; } constexpr MintMatrix operator * (const MintMatrix &r) const { return MintMatrix(*this) *= r; } constexpr vector<mint> operator * (const vector<mint> &v) const { assert(width() == v.size()); vector<mint> res(height(), mint(0)); for (int i = 0; i < height(); i++) for (int j = 0; j < width(); j++) res[i] += val[i][j] * v[j]; return res; } // pow constexpr MintMatrix pow(long long n) const { assert(height() == width()); MintMatrix<mint> res(height(), width()), mul(*this); for (int row = 0; row < height(); ++row) res[row][row] = mint(1); while (n > 0) { if (n & 1) res = res * mul; mul = mul * mul; n >>= 1; } return res; } friend constexpr MintMatrix<mint> pow(const MintMatrix<mint> &mat, long long n) { return mat.pow(n); } // gauss-jordan constexpr int find_pivot(int cur_rank, int col) const { int pivot = -1; for (int row = cur_rank; row < height(); ++row) { if (val[row][col] != 0) { pivot = row; break; } } return pivot; } constexpr void sweep(int cur_rank, int col, int pivot) { swap(val[pivot], val[cur_rank]); auto ifac = val[cur_rank][col].inv(); for (int col2 = 0; col2 < width(); ++col2) { val[cur_rank][col2] *= ifac; } for (int row = 0; row < height(); ++row) { if (row != cur_rank && val[row][col] != 0) { auto fac = val[row][col]; for (int col2 = 0; col2 < width(); ++col2) { val[row][col2] -= val[cur_rank][col2] * fac; } } } } constexpr int gauss_jordan(int not_sweep_width = 0) { int rank = 0; for (int col = 0; col < width(); ++col) { if (col == width() - not_sweep_width) break; int pivot = find_pivot(rank, col); if (pivot == -1) continue; sweep(rank++, col, pivot); } return rank; } constexpr int gauss_jordan(int not_sweep_width, vector<int> &core) { core.clear(); int rank = 0; for (int col = 0; col < width(); ++col) { if (col == width() - not_sweep_width) break; int pivot = find_pivot(rank, col); if (pivot == -1) continue; core.push_back(col); sweep(rank++, col, pivot); } return rank; } friend constexpr int gauss_jordan(MintMatrix<mint> &mat, int not_sweep_width = 0) { return mat.gauss_jordan(not_sweep_width); } // find one solution friend constexpr int linear_equation (const MintMatrix<mint> &mat, const vector<mint> &b, vector<mint> &res) { // extend MintMatrix<mint> A(mat.height(), mat.width() + 1); for (int i = 0; i < mat.height(); ++i) { for (int j = 0; j < mat.width(); ++j) A[i][j] = mat.val[i][j]; A[i].back() = b[i]; } int rank = A.gauss_jordan(1); // check if it has no solution for (int row = rank; row < mat.height(); ++row) if (A[row].back() != 0) return -1; // answer res.assign(mat.width(), 0); for (int i = 0; i < rank; ++i) res[i] = A[i].back(); return rank; } friend constexpr int linear_equation(const MintMatrix<mint> &mat, const vector<mint> &b) { vector<mint> res; return linear_equation(mat, b, res); } // find all solutions friend int linear_equation (const MintMatrix<mint> &mat, const vector<mint> &b, vector<mint> &res, vector<vector<mint>> &zeros) { // extend MintMatrix<mint> A(mat.height(), mat.width() + 1); for (int i = 0; i < mat.height(); ++i) { for (int j = 0; j < mat.width(); ++j) A[i][j] = mat.val[i][j]; A[i].back() = b[i]; } vector<int> core; int rank = A.gauss_jordan(1, core); // check if it has no solution for (int row = rank; row < mat.height(); ++row) { if (A[row].back() != 0) return -1; } // construct the core solution res.assign(mat.width(), mint(0)); for (int i = 0; i < (int)core.size(); i++) res[core[i]] = A[i].back(); // construct the all solutions zeros.clear(); vector<bool> use(mat.width(), 0); for (auto c : core) use[c] = true; for (int j = 0; j < mat.width(); j++) { if (use[j]) continue; vector<mint> zero(mat.width(), mint(0)); zero[j] = mint(1); for (int i = 0; i < (int)core.size(); i++) zero[core[i]] = -A[i][j]; zeros.push_back(zero); } return rank; } // determinant constexpr mint det() const { MintMatrix<mint> A(*this); int rank = 0; mint res = 1; for (int col = 0; col < width(); ++col) { int pivot = A.find_pivot(rank, col); if (pivot == -1) return mint(0); res *= A[pivot][rank]; A.sweep(rank++, col, pivot); } return res; } friend constexpr mint det(const MintMatrix<mint> &mat) { return mat.det(); } }; // characteristic_polynomial // find f(x) = det(xI - B), for N x N mint matrix B, O(N^3) template<class mint> void hessenberg_reduction(MintMatrix<mint> &M) { assert(M.height() == M.width()); int N = (int)M.height(); for (int r = 0; r < N - 2; r++) { int pivot = -1; for (int h = r + 1; h < N; h++) { if (M[h][r] != 0) { pivot = h; break; } } if (pivot == -1) continue; for (int i = 0; i < N; i++) swap(M[r + 1][i], M[pivot][i]); for (int i = 0; i < N; i++) swap(M[i][r + 1], M[i][pivot]); mint ir = M[r + 1][r].inv(); for (int i = r + 2; i < N; i++) { mint ir2 = M[i][r] * ir; for (int j = 0; j < N; j++) M[i][j] -= M[r + 1][j] * ir2; for (int j = 0; j < N; j++) M[j][r + 1] += M[j][i] * ir2; } } } template<class mint> FPS<mint> calc_characteristic_polynomial(MintMatrix<mint> B) { assert(B.height() == B.width()); hessenberg_reduction(B); int N = (int)B.height(); vector<FPS<mint>> res(N + 1); res[0] = {mint(1)}; for (int i = 0; i < N; i++) { res[i + 1].assign(i + 2, mint(0)); for (int j = 0; j < i + 1; j++) res[i + 1][j + 1] += res[i][j]; for (int j = 0; j < i + 1; j++) res[i + 1][j] -= res[i][j] * B[i][i]; mint beta = 1; for (int j = i - 1; j >= 0; j--) { beta *= B[j + 1][j]; mint beta2 = -B[j][i] * beta; for (int k = 0; k < j + 1; k++) res[i + 1][k] += beta2 * res[j][k]; } } return res[N]; } // find f(x) = det(M1x + M0), for given N x N matrix M0, M1, in O(N^3) template<class mint> FPS<mint> calc_det_linear_expression(MintMatrix<mint> M0, MintMatrix<mint> M1) { int N = (int)M0.height(); assert(M0.width() == N && M1.height() == N && M1.width() == N); int con = 0; mint invAB = 1; for (int p = 0; p < N; p++) { int pivot = -1; for (int r = p; r < N; r++) { if (M1[r][p] != mint(0)) { pivot = r; break; } } if (pivot == -1) { con++; if (con > N) return FPS<mint>(N + 1, mint(0)); for (int r = 0; r < p; r++) { mint v = M1[r][p]; M1[r][p] = 0; for (int i = 0; i < N; i++) M0[i][p] -= v * M0[i][r]; } for (int i = 0; i < N; i++) swap(M0[i][p], M1[i][p]); p--; continue; } if (pivot != p) { swap(M1[p], M1[pivot]); swap(M0[p], M0[pivot]); invAB *= -1; } mint v = M1[p][p], iv = v.inv(); invAB *= v; for (int c = 0; c < N; c++) M0[p][c] *= iv, M1[p][c] *= iv; for (int r = 0; r < N; r++) { if (r == p) continue; mint v = M1[r][p]; for (int c = 0; c < N; c++) M0[r][c] -= M0[p][c] * v, M1[r][c] -= M1[p][c] * v; } } for (int r = 0; r < M0.height(); r++) for (int c = 0; c < M0.width(); c++) M0[r][c] *= -1; auto pol = calc_characteristic_polynomial(M0); for (auto &x : pol) x *= invAB; pol.erase(pol.begin(), pol.begin() + con); pol.resize(N + 1); return pol; } //------------------------------// // Examples //------------------------------// // yukicoder No.1907 DETERMINATION void yukicoder_1907() { using mint = Fp<>; int N; cin >> N; MintMatrix<mint> M0(N, N), M1(N, N); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> M0[i][j]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> M1[i][j]; auto res = calc_det_linear_expression(M0, M1); for (int i = 0; i < res.size(); i++) cout << res[i] << '\n'; } int main() { yukicoder_1907(); }