結果

問題 No.1907 DETERMINATION
ユーザー colognecologne
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 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;
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 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();
}
// 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 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)
{
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0