結果
問題 | No.1907 DETERMINATION |
ユーザー | flself |
提出日時 | 2023-10-09 00:08:11 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,829 ms / 4,000 ms |
コード長 | 18,169 bytes |
コンパイル時間 | 3,640 ms |
コンパイル使用メモリ | 272,116 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-07-26 18:16:36 |
合計ジャッジ時間 | 58,777 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 489 ms
6,944 KB |
testcase_08 | AC | 194 ms
6,940 KB |
testcase_09 | AC | 334 ms
6,940 KB |
testcase_10 | AC | 1,065 ms
6,944 KB |
testcase_11 | AC | 313 ms
6,944 KB |
testcase_12 | AC | 1,185 ms
6,940 KB |
testcase_13 | AC | 1,094 ms
6,944 KB |
testcase_14 | AC | 1,052 ms
7,040 KB |
testcase_15 | AC | 196 ms
6,940 KB |
testcase_16 | AC | 66 ms
6,940 KB |
testcase_17 | AC | 987 ms
6,944 KB |
testcase_18 | AC | 748 ms
6,940 KB |
testcase_19 | AC | 19 ms
6,940 KB |
testcase_20 | AC | 1,131 ms
7,040 KB |
testcase_21 | AC | 100 ms
6,940 KB |
testcase_22 | AC | 1,023 ms
6,944 KB |
testcase_23 | AC | 1,296 ms
6,944 KB |
testcase_24 | AC | 361 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 1,219 ms
7,168 KB |
testcase_27 | AC | 1,469 ms
7,168 KB |
testcase_28 | AC | 1,493 ms
7,168 KB |
testcase_29 | AC | 1,474 ms
7,168 KB |
testcase_30 | AC | 2 ms
6,944 KB |
testcase_31 | AC | 1,252 ms
7,040 KB |
testcase_32 | AC | 1,212 ms
6,940 KB |
testcase_33 | AC | 1,204 ms
7,168 KB |
testcase_34 | AC | 1,203 ms
7,040 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 2 ms
6,944 KB |
testcase_38 | AC | 1,204 ms
7,168 KB |
testcase_39 | AC | 1,201 ms
7,040 KB |
testcase_40 | AC | 1,829 ms
7,040 KB |
testcase_41 | AC | 1,225 ms
7,168 KB |
testcase_42 | AC | 1,829 ms
7,040 KB |
testcase_43 | AC | 1,824 ms
7,168 KB |
testcase_44 | AC | 1,393 ms
7,040 KB |
testcase_45 | AC | 1,502 ms
7,040 KB |
testcase_46 | AC | 1,223 ms
6,944 KB |
testcase_47 | AC | 1,206 ms
7,040 KB |
testcase_48 | AC | 1,211 ms
7,168 KB |
testcase_49 | AC | 1,265 ms
7,168 KB |
testcase_50 | AC | 1,222 ms
7,040 KB |
testcase_51 | AC | 1,211 ms
7,168 KB |
testcase_52 | AC | 2 ms
6,940 KB |
testcase_53 | AC | 1,483 ms
6,940 KB |
testcase_54 | AC | 1,489 ms
6,940 KB |
testcase_55 | AC | 2 ms
6,944 KB |
testcase_56 | AC | 1,093 ms
6,940 KB |
testcase_57 | AC | 1,104 ms
6,944 KB |
testcase_58 | AC | 623 ms
7,040 KB |
testcase_59 | AC | 890 ms
6,940 KB |
testcase_60 | AC | 893 ms
7,168 KB |
testcase_61 | AC | 1,029 ms
7,040 KB |
testcase_62 | AC | 898 ms
7,040 KB |
testcase_63 | AC | 1,198 ms
7,040 KB |
testcase_64 | AC | 2 ms
6,940 KB |
testcase_65 | AC | 2 ms
6,940 KB |
testcase_66 | AC | 2 ms
6,944 KB |
ソースコード
#include<bits/stdc++.h> #ifdef LOCAL #include "debugger.hpp" #else #define dbg(...) #endif using i64 = long long; template<class T> constexpr T power(T a, i64 b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; } constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - i64(1.L * a * b / p) * p; res %= p; if (res < 0) { res += p; } return res; } template<i64 P> struct MLong { i64 x; constexpr MLong() : x{} {} constexpr MLong(i64 x) : x{norm(x % getMod())} {} static i64 Mod; constexpr static i64 getMod() { if (P > 0) { return P; } else { return Mod; } } constexpr static int getRoot() { if (getMod() == 1231453023109121) return 3; assert(false); } constexpr static void setMod(i64 Mod_) { Mod = Mod_; } constexpr i64 norm(i64 x) const { if (x < 0) { x += getMod(); } if (x >= getMod()) { x -= getMod(); } return x; } constexpr i64 val() const { return x; } explicit constexpr operator i64() const { return x; } explicit constexpr operator bool() const { return x != 0;} constexpr MLong operator-() const { MLong res; res.x = norm(getMod() - x); return res; } constexpr MLong inv() const { i64 a = getMod(), b = x; i64 y = 0, z = 1; for (; b; ) { i64 k = a / b; std::swap(a -= k * b, b); std::swap(y -= k * z, z); } assert(a == 1); return MLong(y); } constexpr MLong &operator*=(MLong rhs) & { x = mul(x, rhs.x, getMod()); return *this; } constexpr MLong &operator+=(MLong rhs) & { x = norm(x + rhs.x); return *this; } constexpr MLong &operator-=(MLong rhs) & { x = norm(x - rhs.x); return *this; } constexpr MLong &operator/=(MLong rhs) & { return *this *= rhs.inv(); } friend constexpr MLong operator*(MLong lhs, MLong rhs) { MLong res = lhs; res *= rhs; return res; } friend constexpr MLong operator+(MLong lhs, MLong rhs) { MLong res = lhs; res += rhs; return res; } friend constexpr MLong operator-(MLong lhs, MLong rhs) { MLong res = lhs; res -= rhs; return res; } friend constexpr MLong operator/(MLong lhs, MLong rhs) { MLong res = lhs; res /= rhs; return res; } friend constexpr std::istream &operator>>(std::istream &is, MLong &a) { i64 v; is >> v; a = MLong(v); return is; } friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) { return os << a.val(); } friend constexpr bool operator==(MLong lhs, MLong rhs) { return lhs.val() == rhs.val(); } friend constexpr bool operator!=(MLong lhs, MLong rhs) { return lhs.val() != rhs.val(); } }; template<> i64 MLong<0LL>::Mod = i64(1E18) + 9; template<int P> struct MInt { int x; constexpr MInt() : x{} {} constexpr MInt(i64 x) : x{norm(x % getMod())} {} static int Mod; constexpr static int getMod() { if (P > 0) { return P; } else { return Mod; } } constexpr static int getRoot() { if (getMod() == 998244353) return 3; assert(false); } constexpr static void setMod(int Mod_) { Mod = Mod_; } constexpr int norm(int x) const { if (x < 0) { x += getMod(); } if (x >= getMod()) { x -= getMod(); } return x; } constexpr int val() const { return x; } explicit operator MLong<P>() const { return MLong<P>(x); } explicit constexpr operator int() const { return x; } explicit constexpr operator bool() const { return x != 0;} constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; } constexpr MInt inv() const { unsigned a = getMod(), b = x; int y = 0, z = 1; for (; b; ) { int k = a / b; std::swap(a -= k * b, b); std::swap(y -= k * z, z); } assert(a == 1U); return MInt(y); } constexpr MInt &operator*=(MInt rhs) & { x = 1LL * x * rhs.x % getMod(); return *this; } constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; } constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; } constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); } friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; } friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; } friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; } friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; } friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; } friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); } friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); } friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); } }; template<> int MInt<0>::Mod = 998244353; template<int V, int P> constexpr MInt<P> CInv = MInt<P>(V).inv(); constexpr int P = 998244353; using Z = MInt<P>; std::vector<int> rev; std::vector<Z> roots{0, 1}; void dft(std::vector<Z> &a) { int n = a.size(); if ((int)(rev.size()) != n) { int k = __builtin_ctz(n) - 1; rev.resize(n); for (int i = 0; i < n; i++) { rev[i] = rev[i >> 1] >> 1 | (i & 1) << k; } } for (int i = 0; i < n; i++) { if (rev[i] < i) { std::swap(a[i], a[rev[i]]); } } if ((int)(roots.size()) < n) { int k = __builtin_ctz(roots.size()); roots.resize(n); while ((1 << k) < n) { Z e = power(Z(Z::getRoot()), (Z::getMod() - 1) >> (k + 1)); for (int i = 1 << (k - 1); i < (1 << k); i++) { roots[2 * i] = roots[i]; roots[2 * i + 1] = roots[i] * e; } k++; } } for (int k = 1; k < n; k *= 2) { for (int i = 0; i < n; i += 2 * k) { for (int j = 0; j < k; j++) { Z u = a[i + j]; Z v = a[i + j + k] * roots[k + j]; a[i + j] = u + v; a[i + j + k] = u - v; } } } } void idft(std::vector<Z> &a) { int n = a.size(); std::reverse(a.begin() + 1, a.end()); dft(a); Z inv = (1 - Z::getMod()) / n; for (int i = 0; i < n; i++) { a[i] *= inv; } } template<typename T> struct Poly { std::vector<T> a; Poly() {} Poly(const std::vector<T> &a) : a(a) {} Poly(const std::initializer_list<T> &a) : a(a) {} int size() const { return a.size(); } void resize(int n) { a.resize(n); } T operator[](int idx) const { if (idx < size()) { return a[idx]; } else { return 0; } } T &operator[](int idx) { return a[idx]; } Poly mulxk(int k) const { auto b = a; b.insert(b.begin(), k, 0); return Poly(b); } Poly modxk(int k) const { k = std::min(k, size()); return Poly(std::vector<T>(a.begin(), a.begin() + k)); } Poly divxk(int k) const { if (size() <= k) { return Poly(); } return Poly(std::vector<T>(a.begin() + k, a.end())); } friend Poly operator+(const Poly &a, const Poly &b) { std::vector<T> res(std::max(a.size(), b.size())); for (int i = 0; i < (int)(res.size()); i++) { res[i] = a[i] + b[i]; } return Poly(res); } friend Poly operator-(const Poly &a, const Poly &b) { std::vector<T> res(std::max(a.size(), b.size())); for (int i = 0; i < (int)(res.size()); i++) { res[i] = a[i] - b[i]; } return Poly(res); } friend Poly operator*(Poly a, Poly b) { if (a.size() == 0 || b.size() == 0) { return Poly(); } int sz = 1, tot = a.size() + b.size() - 1; while (sz < tot) { sz *= 2; } a.a.resize(sz); b.a.resize(sz); dft(a.a); dft(b.a); for (int i = 0; i < sz; ++i) { a.a[i] = a[i] * b[i]; } idft(a.a); a.resize(tot); return a; } friend Poly operator*(T a, Poly b) { for (int i = 0; i < (int)(b.size()); i++) { b[i] *= a; } return b; } friend Poly operator*(Poly a, T b) { for (int i = 0; i < (int)(a.size()); i++) { a[i] *= b; } return a; } Poly &operator+=(Poly b) { return (*this) = (*this) + b; } Poly &operator-=(Poly b) { return (*this) = (*this) - b; } Poly &operator*=(Poly b) { return (*this) = (*this) * b; } Poly deriv() const { if (a.empty()) { return Poly(); } std::vector<T> res(size() - 1); for (int i = 0; i < size() - 1; ++i) { res[i] = (i + 1) * a[i + 1]; } return Poly(res); } Poly integr() const { std::vector<T> res(size() + 1); for (int i = 0; i < size(); ++i) { res[i + 1] = a[i] / (i + 1); } return Poly(res); } Poly inv(int m) const { Poly x{a[0].inv()}; int k = 1; while (k < m) { k *= 2; x = (x * (Poly{2} - modxk(k) * x)).modxk(k); } return x.modxk(m); } Poly log(int m) const { return (deriv() * inv(m)).integr().modxk(m); } Poly exp(int m) const { Poly x{1}; int k = 1; while (k < m) { k *= 2; x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k); } return x.modxk(m); } Poly pow(int k, int m) const { int i = 0; while (i < size() && a[i].val() == 0) { i++; } if (i == size() || 1LL * i * k >= m) { return Poly(std::vector<T>(m)); } T v = a[i]; auto f = divxk(i) * v.inv(); return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k); } Poly sqrt(int m) const { Poly x{1}; int k = 1; while (k < m) { k *= 2; x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((T::getMod() + 1) / 2); } return x.modxk(m); } Poly mulT(Poly b) const { if (b.size() == 0) { return Poly(); } int n = b.size(); std::reverse(b.a.begin(), b.a.end()); return ((*this) * b).divxk(n - 1); } std::vector<T> eval(std::vector<T> x) const { if (size() == 0) { return std::vector<T>(x.size(), 0); } const int n = std::max((int)(x.size()), size()); std::vector<Poly> q(4 * n); std::vector<T> ans(x.size()); x.resize(n); std::function<void(int, int, int)> build = [&](int p, int l, int r) { if (r - l == 1) { q[p] = Poly{1, -x[l]}; } else { int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); q[p] = q[2 * p] * q[2 * p + 1]; } }; build(1, 0, n); std::function<void(int, int, int, const Poly &)> work = [&](int p, int l, int r, const Poly &num) { if (r - l == 1) { if (l < (int)(ans.size())) { ans[l] = num[0]; } } else { int m = (l + r) / 2; work(2 * p, l, m, num.mulT(q[2 * p + 1]).modxk(m - l)); work(2 * p + 1, m, r, num.mulT(q[2 * p]).modxk(r - m)); } }; work(1, 0, n, mulT(q[1].inv(n))); return ans; } }; template<typename T> T count_minor(const std::vector<std::vector<int>> matrix, int idx = 0, int idy = 0) { assert(matrix.size() == matrix[0].size()); int n = matrix.size(); assert(idx < n && idy < n); if (n == 1) { return 0; } std::vector minor(n-1, std::vector<T>(n-1)); for (int i = 0; i < n; ++i) { if (i == idx) continue; for (int j = 0; j < n; ++j) { if (j == idy) continue; minor[i - (i > idx)][j - (j > idy)] = matrix[i][j]; } } n--; auto gauss=[&]()->T { for (int i = 0; i < n; ++i) { if (minor[i][i] == 0) { for (int j = i + 1; j < n; ++j) { if (minor[j][i]) { // for (int k = 0; k < n; ++k) { // std::swap(minor[i][k], minor[j][k]); // } std::swap(minor[i], minor[j]); break; } } } if (minor[i][i] == 0) { return 0; } for (int j = i + 1; j < n; ++j) { if (i == j) continue; T mul = minor[j][i] / minor[i][i]; for (int k = i; k < n; ++k) { minor[j][k] -= mul * minor[i][k]; } } } T res = 1; for (int i = 0; i < n; ++i) { res *= minor[i][i]; } return res; }; return gauss(); } // Kirchhoff Z Kirchhoff(const std::vector<std::vector<int>> &G) { int n = G.size(); std::vector<std::vector<int>> L(n, std::vector<int>(n)); for (int i = 0; i < n; ++i) { L[i][i] = G[i].size(); for (auto &j : G[i]) { L[i][j]--; } } return count_minor<Z>(L); } /// @param A square matrix of size n /// @return characteristic polynomial of A, which is `det(xI - M)` template <typename T> std::vector<T> char_poly(std::vector<std::vector<T>> M) { int N = M.size(); assert(N == M[0].size()); // Hessenberg Reduction for (int i = 0; i < N - 2; i++) { int p = -1; for (int j = i + 1; j < N; j++) { if (M[j][i] != T(0)) { p = j; break; } } if (p == -1) { continue; } M[i + 1].swap(M[p]); for (int j = 0; j < N; j++) { std::swap(M[j][i + 1], M[j][p]); } T r = T(1) / M[i + 1][i]; for (int j = i + 2; j < N; j++) { T c = M[j][i] * r; for (int k = 0; k < N; k++) M[j][k] -= M[i + 1][k] * c; for (int k = 0; k < N; k++) M[k][i + 1] += M[k][j] * c; } } // La Budde's Method std::vector<std::vector<T>> P = {{T(1)}}; for (int i = 0; i < N; i++) { std::vector<T> f(i + 2, 0); for (int j = 0; j <= i; j++) f[j + 1] += P[i][j]; for (int j = 0; j <= i; j++) f[j] -= P[i][j] * M[i][i]; T b = 1; for (int j = i - 1; j >= 0; j--) { b *= M[j + 1][j]; T h = -M[j][i] * b; for (int k = 0; k <= j; k++) f[k] += h * P[j][k]; } P.push_back(f); } return P.back(); } /// @brief calculate `det(Ax + B)`, where A and B are square matrices of size n /// @tparam T usually Z /// @tparam Matrix usually std::vector<std::vector<T>>, or custom matrix class /// @param A /// @param B /// @return `det(Ax + B)` template <typename T> std::vector<T> det_linear(std::vector<std::vector<T>> A, std::vector<std::vector<T>> B) { int N = A.size(), nu = 0; T det = 1; for (int i = 0; i < N; i++) { // do normal gaussian elimination int p = -1; for (int j = i; j < N; j++) { if (A[j][i] != T(0)) { p = j; break; } } // replace B with A if (p == -1) { // Increase nullity by 1 if (++nu > N) { return std::vector<T>(N + 1, 0); } // i-th column is empty for (int j = 0; j < i; j++) { for (int k = 0; k < N; k++) { B[k][i] -= B[k][j] * A[j][i]; } A[j][i] = 0; } for (int j = 0; j < N; j++) { std::swap(A[j][i], B[j][i]); } // retry --i; continue; } if (p != i) { A[i].swap(A[p]); B[i].swap(B[p]); det = -det; } det *= A[i][i]; T c = T(1) / A[i][i]; for (int j = 0; j < N; j++) { A[i][j] *= c, B[i][j] *= c; } for (int j = 0; j < N; j++) { if (j != i) { T c = A[j][i]; for (int k = 0; k < N; k++) { A[j][k] -= A[i][k] * c, B[j][k] -= B[i][k] * c; } } } } for (auto &y : B) { for (T &x : y) { x = -x; } } auto f = char_poly(B); for (T &x : f) { x *= det; } f.erase(f.begin(), f.begin() + nu); f.resize(N + 1); return f; } void solv() { int n; std::cin >> n; std::vector<std::vector<Z>> D1(n, std::vector<Z>(n)); auto D2 = D1; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std::cin >> D2[i][j]; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std::cin >> D1[i][j]; } } auto poly = det_linear(D1, D2); for (int i = 0; i <= n; ++i) { if (i >= poly.size()) { std::cout << "0\n"; } else { std::cout << poly[i] << '\n'; } } } signed main() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr); int tt = 1; // std::cin >> tt; while (tt--) { solv(); } return 0; }