結果
| 問題 | No.1907 DETERMINATION |
| コンテスト | |
| ユーザー |
 えりす
|
| 提出日時 | 2026-06-03 02:02:53 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,843 bytes |
| 記録 | |
| コンパイル時間 | 2,347 ms |
| コンパイル使用メモリ | 234,304 KB |
| 実行使用メモリ | 7,520 KB |
| 最終ジャッジ日時 | 2026-06-03 02:03:27 |
| 合計ジャッジ時間 | 9,957 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 6 TLE * 1 -- * 56 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
long long pw(long long a, long long b) {
long long res = 1;
a %= MOD;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
long long inv(long long a) { return pw(a, MOD - 2); }
int n;
vector<vector<long long>> a, b;
vector<vector<long long>> mul(const vector<vector<long long>>& x, const vector<vector<long long>>& y) {
vector<vector<long long>> c(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++) {
if (x[i][k] == 0) continue;
long long v = x[i][k];
for (int j = 0; j < n; j++)
c[i][j] = (c[i][j] + v * y[k][j]) % MOD;
}
return c;
}
vector<long long> mv(const vector<vector<long long>>& x, const vector<long long>& v) {
vector<long long> res(n, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i] = (res[i] + x[i][j] * v[j]) % MOD;
return res;
}
long long det(vector<vector<long long>> a) {
long long res = 1;
for (int i = 0; i < n; i++) {
if (a[i][i] == 0) {
bool ok = false;
for (int j = i + 1; j < n; j++) {
if (a[j][i]) {
swap(a[i], a[j]);
res = (MOD - res) % MOD;
ok = true;
break;
}
}
if (!ok) return 0;
}
long long t = inv(a[i][i]);
res = res * a[i][i] % MOD;
for (int j = i + 1; j < n; j++) {
if (a[j][i]) {
long long f = a[j][i] * t % MOD;
for (int k = i; k < n; k++)
a[j][k] = (a[j][k] - f * a[i][k] % MOD + MOD) % MOD;
}
}
}
return res;
}
vector<vector<long long>> minv(vector<vector<long long>> a) {
vector<vector<long long>> c(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) c[i][i] = 1;
for (int i = 0; i < n; i++) {
if (a[i][i] == 0) {
for (int j = i + 1; j < n; j++) {
if (a[j][i]) {
swap(a[i], a[j]);
swap(c[i], c[j]);
break;
}
}
}
long long t = inv(a[i][i]);
for (int j = 0; j < n; j++) {
a[i][j] = a[i][j] * t % MOD;
c[i][j] = c[i][j] * t % MOD;
}
for (int j = 0; j < n; j++) {
if (i != j && a[j][i]) {
long long f = a[j][i];
for (int k = 0; k < n; k++) {
a[j][k] = (a[j][k] - f * a[i][k] % MOD + MOD) % MOD;
c[j][k] = (c[j][k] - f * c[i][k] % MOD + MOD) % MOD;
}
}
}
}
return c;
}
vector<long long> bm(vector<long long> s) {
int m = s.size();
vector<long long> c = {1}, b = {1};
int l = 0, cnt = 1;
long long ib = 1;
for (int i = 0; i < m; i++) {
long long d = s[i];
for (int j = 1; j <= l; j++)
d = (d + c[j] * s[i - j]) % MOD;
if (d == 0) { cnt++; continue; }
vector<long long> tmp = c;
long long f = d * inv(ib) % MOD;
if ((int)c.size() < (int)b.size() + cnt)
c.resize(b.size() + cnt, 0);
for (int j = 0; j < (int)b.size(); j++)
c[j + cnt] = (c[j + cnt] - f * b[j] % MOD + MOD) % MOD;
if (2 * l <= i) {
l = i + 1 - l;
b = tmp;
ib = d;
cnt = 1;
} else {
cnt++;
}
}
c.resize(l + 1);
return c;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n, vector<long long>(n));
b.assign(n, vector<long long>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> b[i][j];
int t = 0;
long long d0 = 0;
vector<vector<long long>> x;
for (t = 0; t <= n; t++) {
x.assign(n, vector<long long>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
x[i][j] = (a[i][j] + (long long)t * b[i][j]) % MOD;
d0 = det(x);
if (d0 != 0) break;
}
if (d0 == 0) {
for (int i = 0; i <= n; i++) cout << "0\n";
return 0;
}
vector<vector<long long>> c = mul(minv(x), b);
mt19937 rg(42);
uniform_int_distribution<int> rd(1, MOD - 1);
vector<long long> v(n);
for (int i = 0; i < n; i++) v[i] = rd(rg);
vector<long long> s(2 * n);
vector<long long> w = v;
for (int i = 0; i < 2 * n; i++) {
s[i] = w[0];
w = mv(c, w);
}
vector<long long> p = bm(s);
reverse(p.begin(), p.end());
int deg = p.size() - 1;
if (deg == n) {
vector<long long> y(n + 1);
for (int j = 0; j <= n; j++) {
long long sg = (j % 2 == 0) ? 1 : MOD - 1;
y[j] = sg * p[deg - j] % MOD * d0 % MOD;
}
vector<vector<long long>> cb(n + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= n; i++) {
cb[i][0] = cb[i][i] = 1;
for (int j = 1; j < i; j++)
cb[i][j] = (cb[i - 1][j - 1] + cb[i - 1][j]) % MOD;
}
vector<long long> pt(n + 1, 1);
long long nt = (MOD - t) % MOD;
for (int i = 1; i <= n; i++)
pt[i] = pt[i - 1] * nt % MOD;
vector<long long> ans(n + 1, 0);
for (int k = 0; k <= n; k++)
for (int j = k; j <= n; j++)
ans[k] = (ans[k] + y[j] * cb[j][k] % MOD * pt[j - k]) % MOD;
for (int i = 0; i <= n; i++) cout << ans[i] << "\n";
} else {
vector<long long> d(n + 1);
for (int xx = 0; xx <= n; xx++) {
vector<vector<long long>> m2(n, vector<long long>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
m2[i][j] = (a[i][j] + (long long)xx * b[i][j]) % MOD;
d[xx] = det(m2);
}
for (int k = 1; k <= n; k++)
for (int i = n; i >= k; i--)
d[i] = (d[i] - d[i - 1] + MOD) % MOD * inv(k) % MOD;
vector<vector<long long>> ss(n + 1, vector<long long>(n + 1, 0));
ss[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
ss[i][j] = (ss[i - 1][j - 1] - (long long)(i - 1) * ss[i - 1][j] % MOD + MOD) % MOD;
vector<long long> ans(n + 1, 0);
for (int k = 0; k <= n; k++)
for (int j = k; j <= n; j++)
ans[k] = (ans[k] + d[j] * ss[j][k]) % MOD;
for (int i = 0; i <= n; i++) cout << ans[i] << "\n";
}
return 0;
}