結果
問題 | No.1907 DETERMINATION |
ユーザー |
|
提出日時 | 2022-05-20 15:02:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 650 ms / 4,000 ms |
コード長 | 3,723 bytes |
コンパイル時間 | 1,325 ms |
コンパイル使用メモリ | 118,056 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-09-19 23:00:08 |
合計ジャッジ時間 | 23,924 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 63 |
ソースコード
#include <algorithm>#include <vector>// calculates det(xI-M)template <typename T>std::vector<T> char_poly(std::vector<std::vector<T>> M){int N = M.size();// Hessenberg Reductionfor (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;std::swap(M[i + 1], 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 Methodstd::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();}// Calculates 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 eliminationint p = -1;for (int j = i; j < N; j++)if (A[j][i] != T(0)){p = j;break;}// replace B with Aif (p == -1){// Increase nullity by 1if (++nu > N)return std::vector<T>(N + 1, 0);// i-th column is emptyfor (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){std::swap(A[i], A[p]);std::swap(B[i], 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;}#include <iostream>#include <atcoder/modint>using namespace std;using Mint = atcoder::modint998244353;int main(){ios::sync_with_stdio(false);cin.tie(0);int N;cin >> N;vector<vector<Mint>> A(N, vector<Mint>(N)), B = A;for (auto &y : B)for (auto &x : y){int v;cin >> v;x = v;}for (auto &y : A)for (auto &x : y){int v;cin >> v;x = v;}auto poly = det_linear(A, B);for (auto v : poly)cout << v.val() << endl;}