結果
問題 | No.1907 DETERMINATION |
ユーザー | tokusakurai |
提出日時 | 2023-10-15 11:52:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,247 ms / 4,000 ms |
コード長 | 5,755 bytes |
コンパイル時間 | 2,443 ms |
コンパイル使用メモリ | 213,216 KB |
実行使用メモリ | 7,044 KB |
最終ジャッジ日時 | 2023-10-15 11:53:41 |
合計ジャッジ時間 | 46,112 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,368 KB |
testcase_01 | AC | 2 ms
4,372 KB |
testcase_02 | AC | 1 ms
4,368 KB |
testcase_03 | AC | 2 ms
4,368 KB |
testcase_04 | AC | 2 ms
4,368 KB |
testcase_05 | AC | 1 ms
4,368 KB |
testcase_06 | AC | 1 ms
4,368 KB |
testcase_07 | AC | 299 ms
5,308 KB |
testcase_08 | AC | 116 ms
4,424 KB |
testcase_09 | AC | 204 ms
4,944 KB |
testcase_10 | AC | 872 ms
6,808 KB |
testcase_11 | AC | 308 ms
5,348 KB |
testcase_12 | AC | 780 ms
6,796 KB |
testcase_13 | AC | 718 ms
6,708 KB |
testcase_14 | AC | 707 ms
6,836 KB |
testcase_15 | AC | 148 ms
4,748 KB |
testcase_16 | AC | 43 ms
4,368 KB |
testcase_17 | AC | 822 ms
6,872 KB |
testcase_18 | AC | 508 ms
5,936 KB |
testcase_19 | AC | 12 ms
4,368 KB |
testcase_20 | AC | 756 ms
6,924 KB |
testcase_21 | AC | 61 ms
4,372 KB |
testcase_22 | AC | 846 ms
5,420 KB |
testcase_23 | AC | 907 ms
6,852 KB |
testcase_24 | AC | 222 ms
4,892 KB |
testcase_25 | AC | 2 ms
4,372 KB |
testcase_26 | AC | 761 ms
6,844 KB |
testcase_27 | AC | 980 ms
7,036 KB |
testcase_28 | AC | 1,006 ms
6,896 KB |
testcase_29 | AC | 996 ms
6,896 KB |
testcase_30 | AC | 2 ms
4,372 KB |
testcase_31 | AC | 781 ms
6,904 KB |
testcase_32 | AC | 757 ms
6,884 KB |
testcase_33 | AC | 779 ms
6,848 KB |
testcase_34 | AC | 755 ms
6,896 KB |
testcase_35 | AC | 2 ms
4,372 KB |
testcase_36 | AC | 2 ms
4,368 KB |
testcase_37 | AC | 2 ms
4,368 KB |
testcase_38 | AC | 756 ms
6,912 KB |
testcase_39 | AC | 779 ms
6,908 KB |
testcase_40 | AC | 1,247 ms
6,848 KB |
testcase_41 | AC | 755 ms
6,892 KB |
testcase_42 | AC | 1,242 ms
7,044 KB |
testcase_43 | AC | 1,224 ms
6,848 KB |
testcase_44 | AC | 908 ms
6,952 KB |
testcase_45 | AC | 1,005 ms
6,892 KB |
testcase_46 | AC | 782 ms
6,788 KB |
testcase_47 | AC | 755 ms
6,888 KB |
testcase_48 | AC | 779 ms
7,044 KB |
testcase_49 | AC | 827 ms
6,840 KB |
testcase_50 | AC | 756 ms
6,852 KB |
testcase_51 | AC | 780 ms
6,852 KB |
testcase_52 | AC | 2 ms
4,372 KB |
testcase_53 | AC | 1,050 ms
5,664 KB |
testcase_54 | AC | 1,027 ms
5,624 KB |
testcase_55 | AC | 1 ms
4,368 KB |
testcase_56 | AC | 1,035 ms
5,624 KB |
testcase_57 | AC | 1,032 ms
5,616 KB |
testcase_58 | AC | 829 ms
6,848 KB |
testcase_59 | AC | 591 ms
6,836 KB |
testcase_60 | AC | 589 ms
6,836 KB |
testcase_61 | AC | 735 ms
6,848 KB |
testcase_62 | AC | 588 ms
6,852 KB |
testcase_63 | AC | 780 ms
6,836 KB |
testcase_64 | AC | 2 ms
4,368 KB |
testcase_65 | AC | 2 ms
4,372 KB |
testcase_66 | AC | 1 ms
4,368 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; template <typename T> void print(const vector<T> &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); if (v.empty()) cout << '\n'; } constexpr int MOD = 998244353; template <int mod> struct Mod_Int { int x; Mod_Int() : x(0) {} Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} static int get_mod() { return mod; } Mod_Int &operator+=(const Mod_Int &p) { if ((x += p.x) >= mod) x -= mod; return *this; } Mod_Int &operator-=(const Mod_Int &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } Mod_Int &operator*=(const Mod_Int &p) { x = (int)(1LL * x * p.x % mod); return *this; } Mod_Int &operator/=(const Mod_Int &p) { *this *= p.inverse(); return *this; } Mod_Int &operator++() { return *this += Mod_Int(1); } Mod_Int operator++(int) { Mod_Int tmp = *this; ++*this; return tmp; } Mod_Int &operator--() { return *this -= Mod_Int(1); } Mod_Int operator--(int) { Mod_Int tmp = *this; --*this; return tmp; } Mod_Int operator-() const { return Mod_Int(-x); } Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; } Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; } Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; } Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; } bool operator==(const Mod_Int &p) const { return x == p.x; } bool operator!=(const Mod_Int &p) const { return x != p.x; } Mod_Int inverse() const { assert(*this != Mod_Int(0)); return pow(mod - 2); } Mod_Int pow(long long k) const { Mod_Int now = *this, ret = 1; for (; k > 0; k >>= 1, now *= now) { if (k & 1) ret *= now; } return ret; } friend ostream &operator<<(ostream &os, const Mod_Int &p) { return os << p.x; } friend istream &operator>>(istream &is, Mod_Int &p) { long long a; is >> a; p = Mod_Int<mod>(a); return is; } }; using mint = Mod_Int<MOD>; template <typename T> vector<T> characteristic_polynomial(vector<vector<T>> A) { int n = A.size(); for (int j = 0; j < n - 2; j++) { for (int i = j + 2; i < n; i++) { if (A[i][j] != 0) { swap(A[j + 1], A[i]); for (int k = 0; k < n; k++) swap(A[k][j + 1], A[k][i]); break; } } if (A[j + 1][j] != 0) { T inv = A[j + 1][j].inverse(); for (int i = j + 2; i < n; i++) { T c = A[i][j] * inv; for (int k = j; k < n; k++) A[i][k] -= A[j + 1][k] * c; for (int k = 0; k < n; k++) A[k][j + 1] += A[k][i] * c; } } } vector<vector<T>> p(n + 1); p[0] = {1}; for (int i = 0; i < n; i++) { p[i + 1].assign(i + 2, 0); for (int j = 0; j <= i; j++) { p[i + 1][j + 1] += p[i][j]; p[i + 1][j] -= p[i][j] * A[i][i]; } T c = 1; for (int k = 1; k <= i; k++) { c *= -A[i + 1 - k][i - k]; T x = c * (k & 1 ? A[i - k][i] : -A[i - k][i]); for (int j = 0; j <= i - k; j++) p[i + 1][j] += p[i - k][j] * x; } } return p[n]; } template <typename T> vector<T> linear_funcion_matrix_determinant(vector<vector<T>> A0, vector<vector<T>> A1) { int n = A0.size(); T tmp = 1; int deg = 0; for (int j = 0; j < n; j++) { while (deg <= n) { for (int i = j - 1; i >= 0; i--) { T y = A1[i][j]; for (int k = 0; k < n; k++) { A0[k][j] -= A0[k][i] * y; A1[k][j] -= A1[k][i] * y; } } for (int i = j + 1; i < n; i++) { if (A1[i][j] != 0) { swap(A0[j], A0[i]); swap(A1[j], A1[i]); tmp *= -1; break; } } if (A1[j][j] != 0) break; deg++; for (int i = 0; i < n; i++) { A1[i][j] = A0[i][j]; A0[i][j] = 0; } } if (deg > n) return vector<T>(n + 1, 0); T x = A1[j][j].inverse(); tmp *= A1[j][j]; for (int k = 0; k < n; k++) { A0[j][k] *= x; A1[j][k] *= x; } for (int i = 0; i < n; i++) { if (i != j) { T y = A1[i][j]; for (int k = 0; k < n; k++) { A0[i][k] -= A0[j][k] * y; A1[i][k] -= A1[j][k] * y; } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) A0[i][j] *= -1; } auto f = characteristic_polynomial(A0); vector<T> p(n + 1, 0); for (int i = deg; i <= n; i++) p[i - deg] += f[i] * tmp; return p; } int main() { int N; cin >> N; vector A0(N, vector(N, mint(0))), A1(N, vector(N, mint(0))); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cin >> A0[i][j]; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cin >> A1[i][j]; } auto p = linear_funcion_matrix_determinant(A0, A1); for (int i = 0; i <= N; i++) cout << p[i] << '\n'; }