結果
| 問題 |
No.1907 DETERMINATION
|
| ユーザー |
 vjudge1
|
| 提出日時 | 2025-03-30 13:18:37 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,930 bytes |
| コンパイル時間 | 6,884 ms |
| コンパイル使用メモリ | 498,288 KB |
| 実行使用メモリ | 12,532 KB |
| 最終ジャッジ日時 | 2025-03-30 13:18:54 |
| 合計ジャッジ時間 | 16,776 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 TLE * 1 -- * 1 |
| other | -- * 63 |
コンパイルメッセージ
main.cpp:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
main.cpp:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
main.cpp:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
main.cpp:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
main.cpp:58:16: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
58 | LL P(LL x, LL y) {
| ^
main.cpp:58:16: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
main.cpp:58:16: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
main.cpp:58:16: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
main.cpp:66:11: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
66 | void Init() { // ????????
| ^
main.cpp:66:11: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
main.cpp:66:11: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
main.cpp:66:11: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
main.cpp:102:9: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
102 | void Dp() {
| ^
main.cpp:102:9: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimiz
ソースコード
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 405, kM = 998244353;
LL a[kMaxN][kMaxN], b[kMaxN][kMaxN], f[kMaxN][kMaxN], n, val = 1, cnt;
LL P(LL x, LL y) {
LL ans = 1;
for (LL i = 1; i <= y; i <<= 1, x = x * x % kM) {
(y & i) && (ans = ans * x % kM);
}
return ans;
}
void Init() { // ????????
for (int i = 1; i <= n; i++) { // ?? i ?? i+1 ??? 1
int pos = 0;
for (int j = i + 1; j <= n; j++) {
if (a[j][i]) {
pos = j;
break;
}
}
if (!pos) {
continue;
}
swap(a[i + 1], a[pos]);
for (int k = 1; k <= n; k++) {
swap(a[k][i + 1], a[k][pos]);
}
LL f = a[i + 1][i], inv = P(f, kM - 2);
for (int j = i; j <= n; j++) {
a[i + 1][j] = a[i + 1][j] * inv % kM;
}
for (int j = 1; j <= n; j++) {
a[j][i + 1] = a[j][i + 1] * f % kM;
}
for (int j = i + 2; j <= n; j++) {
LL val = a[j][i];
for (int k = 1; k <= n; k++) {
a[k][i + 1] = (a[k][i + 1] + a[k][j] * val) % kM;
}
val = (kM - val) % kM;
for (int k = i; k <= n; k++) {
a[j][k] = (a[j][k] + a[i + 1][k] * val) % kM;
}
}
}
}
void Dp() {
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
LL val = kM - 1;
for (int j = i; j >= 1; j--) {
LL g = val * a[j][i] % kM;
for (int k = 0; k < j; k++) {
f[i][k] = (f[i][k] + g * f[j - 1][k]) % kM;
}
val = val * a[j][j - 1] % kM;
}
for (int k = 1; k <= i; k++) {
f[i][k] = (f[i - 1][k - 1] + f[i][k]) % kM;
}
}
}
void Work(int x) { // ?(x,x)???0
for (int i = 1; i < x; i++) { // ?x??i?
// ?? i ?????????
for (int j = 1; j <= n; j++) {
a[j][x] = (a[j][x] - a[j][i] * b[i][x]) % kM;
}
b[i][x] = 0;
}
for (int i = 1; i <= n; i++) {
b[i][x] = a[i][x], a[i][x] = 0;
}
}
void Debug() {
cout << "a:\n";
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
cout << a[x][y] << " ";
}
cout << "\n";
}
cout << "b:\n";
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
cout << b[x][y] << " ";
}
cout << "\n";
}
}
void Calc() {
// ????????
for (int i = 1; i <= n; i++) {
int p = 0;
for (int j = i; j <= n; j++) {
if (b[j][i]) {
p = j;
break;
}
}
if (!p) {
cnt++;
Work(i), i--;
} else {
if (p != i) {
swap(b[i], b[p]), swap(a[i], a[p]);
val = (kM - val) % kM;
}
val = val * b[i][i] % kM;
LL v = P(b[i][i], kM - 2);
for (int j = n; j >= 1; j--) {
a[i][j] = a[i][j] * v % kM;
b[i][j] = b[i][j] * v % kM;
}
for (int j = 1; j <= n; j++) {
if (i != j) {
LL x = b[j][i];
for (int k = n; k >= 1; k--) {
a[j][k] = (a[j][k] - x * a[i][k]) % kM;
b[j][k] = (b[j][k] - x * b[i][k]) % kM;
}
}
}
// Debug();
}
}
// ???????
for (int i = n; i >= 1; i--) { // ?i?
for (int j = i + 1; j <= n; j++) { // ???j?
LL val = b[i][j];
for (int k = 1; k <= n; k++) {
b[i][k] = (b[i][k] - b[j][k] * val) % kM;
a[i][k] = (a[i][k] - a[j][k] * val) % kM;
}
}
}
// Debug();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] = (a[i][j] + kM) % kM;
a[i][j] = (kM - a[i][j]) % kM;
}
}
}
int main() {
ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> b[i][j];
}
}
// cout << "\n\n\n\n\n\n";
Calc();
Init();
Dp();
val = (val % kM + kM) % kM;
for (int i = 0; i <= n - cnt; i++) {
cout << f[n][i + cnt] * val % kM << "\n";
}
for (int i = 1; i <= cnt; i++) {
cout << 0 << "\n";
}
return 0;
}