結果
| 問題 | No.1907 DETERMINATION |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-01-09 07:32:04 |
| 言語 | Java (openjdk 25.0.1) |
| 結果 |
AC
|
| 実行時間 | 2,143 ms / 4,000 ms |
| コード長 | 18,749 bytes |
| 記録 | |
| コンパイル時間 | 3,342 ms |
| コンパイル使用メモリ | 98,788 KB |
| 実行使用メモリ | 60,192 KB |
| 最終ジャッジ日時 | 2026-01-09 07:33:16 |
| 合計ジャッジ時間 | 69,173 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 63 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Optional;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.DoubleUnaryOperator;
import java.util.function.IntBinaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
class Matrix {
/**
* B = P⁻¹AP s.t. B[i][j] = 0 if i ≥ j + 2 となる B を返す。
*
* @param A
* @param mod
* @return */
public static long[][] hessenbergReductionOnFp(long[][] A, long mod) {
/* 左から掛けたとき、i行目にj行目を足す行列 P がある。
P = [1 1]
[0 1]
それに対して P⁻¹ は右から掛けるとj列目にi列目が(-1)倍して足される。
P = [1 -1]
[0 1]
左から掛けたとき、i行目とj行目をswapする行列 P がある。
P = [0 1]
[1 0]
それに対して P⁻¹ = Pは右から掛けるとi列目とi列目がswapされる。
P = [0 1]
[1 0]
*/
long[][] B = ArrayUtils.copy(A);
if (B.length != B[0].length) {
throw new AssertionError();
}
int N = B.length;
for (int i = 0; i < (N - 2); i++) {
int p = i + 1;
while ((p < N) && (B[p][i] == 0)) {
++p;
}
if (p == N) {
continue;
}
if ((i + 1) != p) {
ArrayUtils.swap(B[i + 1], B[p]);
ArrayUtils.swapColumns(i + 1, p, B);
}
// A[i+1][i] ≠ 0
long inv = MathUtils.modInv(B[i + 1][i], mod);
for (int j = i + 2; j < N; j++) {
long c = (inv * B[j][i]) % mod;
for (int k = 0; k < N; k++) {
B[j][k] = (B[j][k] + (B[i + 1][k] * (mod - c))) % mod;
}
for (int k = 0; k < N; k++) {
B[k][i + 1] = (B[k][i + 1] + (B[k][j] * c)) % mod;// i列目ではなく、i+1列目に足されるのでok
}
}
}
return B;
}
/**
* det(Ix-A)
*
* @param A
* @param mod
* @return https://judge.yosupo.jp/submission/344336
*/
public static long[] characteristicPolynomialOnFp(long[][] A, long mod) {
if (A.length == 0) {
return new long[]{ 1 };
}
if (A.length != A[0].length) {
throw new AssertionError();
}
long[][] B = Matrix.hessenbergReductionOnFp(A, mod);
int N = A.length;
long[][] f = new long[N + 1][N + 1];
for (int i = 0; i < f.length; i++) {
f[i][i] = 1;
}
// f[i][j] = Π A[k+1][k] for i ≤ k < j
for (int w = 1; w <= N; ++w) {
for (int i = 0; ((i + w) <= N) && ((i + 1) < N); i++) {
f[i][i + w] = (f[i + 1][i + w] * B[i + 1][i]) % mod;
}
}
long[][] g = new long[N + 1][1];
g[0] = new long[]{ 1 };
// g[i] = B の 0,1,..,i-1 行目と 0,1,..,i-1 列目からなる部分行列の特性多項式
for (int i = 0; i < N; i++) {
g[i + 1] = PolynomialFp.add(g[i + 1], PolynomialFp.mul(g[i], new long[]{ mod - B[i][i], 1 }));
for (int j = i + 1; j < N; j++) {
long c = mod - ((f[i][j] * B[i][j]) % mod);
g[j + 1] = PolynomialFp.add(g[j + 1], PolynomialFp.mul(g[i], c));
}
}
return g[N];
}
}
class FastScanner {
private static FastScanner instance = null;
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private FastScanner() {
}
public static FastScanner getInstance() {
if (instance == null) {
instance = new FastScanner();
}
return instance;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private int readByte() {
if (hasNextByte()) {
return buffer[ptr++];
} else {
return -1;
}
}
private boolean isPrintableChar(int c) {
return (33 <= c) && (c <= 126);
}
public boolean hasNext() {
while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
ptr++;
}
return hasNextByte();
}
public long nextLong() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
while ((b >= '0') && (b <= '9')) {
// n = n * 10 + (b - '0');
n = ((n << 1) + (n << 3)) + (b - '0');
b = readByte();
}
return minus ? -n : n;
}
public int nextInt() {
return ((int) (nextLong()));
}
public long[][] nextLongs(int H, int W) {
long[][] a = new long[H][W];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
a[i][j] = nextLong();
}
}
return a;
}
}
class MergeFiles {}
class PolynomialFp {
public static final long mod = 998244353;// 119×2^{23}+1
static long[][] bitreversedRoots = new long[30][];
static long[][] bitreversedInvRoots = new long[30][];
static long ADD(long a, long b) {
long sum = a + b;
return sum >= mod ? sum - mod : sum;
}
static long SUB(long a, long b) {
return ADD(a, mod - b);
}
static void prepareRoots(int n) {
int sz = Integer.numberOfTrailingZeros(n);
if (bitreversedRoots[sz] != null) {
return;
}
long g = 3;
long root = MathUtils.modPow(g, (mod - 1) / n, mod);
long iroot = MathUtils.modInv(root, mod);
bitreversedRoots[sz] = new long[n];
bitreversedInvRoots[sz] = new long[n];
for (int n_ = n / 2; n_ >= 1; n_ /= 2 , root = (root * root) % mod , iroot = (iroot * iroot) % mod) {
long w = 1;
long iw = 1;
for (int j = 0; j < n_; ++j) {
bitreversedRoots[sz][n_ + j] = w;
bitreversedInvRoots[sz][n_ + j] = iw;
w = (w * root) % mod;
iw = (iw * iroot) % mod;
}
int cur = 0;
for (int j = 0; j < n_; ++j) {
if (cur < j) {
ArrayUtils.swap(n_ + cur, n_ + j, bitreversedRoots[sz]);
ArrayUtils.swap(n_ + cur, n_ + j, bitreversedInvRoots[sz]);
}
for (int k = n_ / 2; k > (cur ^= k); k /= 2);
}
}
}
/**
* Scott, Michael. "A note on the implementation of the number theoretic transform." IMA International Conference on Cryptography and Coding. Cham: Springer International Publishing, 2017.
*
* @param a
*/
public static void fftTobitReversed(long[] a) {
int n = a.length;
int sz = Integer.numberOfTrailingZeros(a.length);
if (bitreversedRoots[sz] == null) {
prepareRoots(a.length);
}
for (int m = 1, t = n / 2; m <= (n / 2); m *= 2 , t /= 2) {
for (int i = 0, k = 0; i < m; ++i , k += 2 * t) {
long S = bitreversedRoots[sz][m + i];
for (int j = k; j < (k + t); ++j) {
long u = a[j];
long v = (a[j + t] * S) % mod;
a[j] = ADD(u, v);
a[j + t] = SUB(u, v);
}
}
}
}
/**
* Scott, Michael. "A note on the implementation of the number theoretic transform." IMA International Conference on Cryptography and Coding. Cham: Springer International Publishing, 2017.
*
* @param a
*/
public static void ifftFromBitreversed(long[] a) {
long invN = MathUtils.modInv(a.length, mod);
int n = a.length;
int sz = Integer.numberOfTrailingZeros(n);
if (bitreversedInvRoots[sz] == null) {
prepareRoots(a.length);
}
for (int m = n / 2, t = 1; m >= 1; m /= 2 , t *= 2) {
for (int i = 0, k = 0; i < m; ++i , k += 2 * t) {
long S = bitreversedInvRoots[sz][m + i];
if (m == 1) {
S = (S * invN) % mod;
}
for (int j = k; j < (k + t); ++j) {
long u = a[j];
long v = a[j + t];
if (m == 1) {
a[j] = ((u + v) * invN) % mod;
} else {
a[j] = ADD(u, v);
}
a[j + t] = (((u + mod) - v) * S) % mod;
}
}
}
}
public static long[] add(long[] a, long[] b) {
long[] ret = new long[Math.max(a.length, b.length)];
for (int i = 0; i < ret.length; ++i) {
ret[i] = ADD(i < a.length ? a[i] : 0, i < b.length ? b[i] : 0);
}
return ret;
}
static long[] mulFFT(long[] a, long[] b) {
int n = 1;
int len = (a.length + b.length) - 1;
while (n < ((a.length + b.length) - 1)) {
n *= 2;
}
a = Arrays.copyOf(a, n);
b = Arrays.copyOf(b, n);
prepareRoots(n);
fftTobitReversed(a);
fftTobitReversed(b);
for (int i = 0; i < a.length; ++i) {
a[i] = (a[i] * b[i]) % mod;
}
ifftFromBitreversed(a);
return resize(a, len);
}
public static long[] mulNaive(long[] a, long[] b) {
long[] ret = new long[(a.length + b.length) - 1];
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j < b.length; ++j) {
ret[i + j] += a[i] * b[j];
ret[i + j] %= mod;
}
}
return ret;
}
/**
* [-mod+1, mod-1]の範囲外の要素があると、ADD/SUBでバグる。
*
* @param a
* @param b
* @return */
public static long[] mul(long[] a, long[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] < 0) {
a[i] += mod;
}
}
for (int i = 0; i < b.length; i++) {
if (b[i] < 0) {
b[i] += mod;
}
}
if ((((a.length + b.length) - 1) <= 512) || (Math.min(a.length, b.length) <= 10)) {
return mulNaive(a, b);
} else {
return mulFFT(a, b);
}
}
public static long[] mul(long[] a, long b) {
long[] ret = new long[a.length];
for (int i = 0; i < a.length; ++i) {
ret[i] = (a[i] * b) % mod;
}
return ret;
}
static long[] resize(long[] a, int len) {
return Arrays.copyOf(a, len);
}
}
class ArrayUtils {
public static void swap(int i, int j, long[] A) {
if (i == j) {
return;
}
long tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
public static void swap(long[] A, long[] B) {
if (A.length != B.length) {
throw new AssertionError();
}
for (int i = 0; i < A.length; i++) {
long tmp = A[i];
A[i] = B[i];
B[i] = tmp;
}
}
public static void swapColumns(int i, int j, long[][] a) {
if (i == j) {
return;
}
for (int k = 0; k < a.length; k++) {
var tmp = a[k][i];
a[k][i] = a[k][j];
a[k][j] = tmp;
}
}
public static long[][] copy(long[][] a) {
long[][] b = new long[a.length][];
Arrays.setAll(b, i -> Arrays.copyOf(a[i], a[i].length));
return b;
}
}
class MyPrintWriter extends PrintWriter {
private static MyPrintWriter instance = null;
private MyPrintWriter() {
super(System.out);
}
public static MyPrintWriter getInstance() {
if (instance == null) {
instance = new MyPrintWriter();
}
return instance;
}
public void println(long[] a, String separator) {
for (int i = 0; i < a.length; ++i) {
super.print(a[i] + (i == (a.length - 1) ? "\n" : separator));
}
}
}
class MathUtils {
public static long modPow(long a, long n, long mod) {
if (n < 0) {
long inv = MathUtils.modInv(a, mod);
return MathUtils.modPow(inv, -n, mod);
}
if (n == 0) {
return 1;
}
return (MathUtils.modPow((a * a) % mod, n / 2, mod) * ((n % 2) == 1 ? a : 1)) % mod;
}
/**
* 拡張ユークリッドの互除法で逆元を求める。
*
* @param a
* @param mod
* @return */
public static long modInv(long a, long mod) {
a = ((a % mod) + mod) % mod;
long[] f0 = new long[]{ 1, 0, mod };
long[] f1 = new long[]{ 0, 1, a };
while (f1[2] != 0) {
long q = f0[2] / f1[2];
for (int i = 0; i < 3; i++) {
f0[i] -= q * f1[i];
}
ArrayUtils.swap(f0, f1);
}
return f0[1] < 0 ? mod + f0[1] : f0[1];
}
}
public class Main implements Runnable {
public static void main(String[] args) throws IOException {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
// new Main().gen();
// Runtime runtime = Runtime.getRuntime();
// new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).run();
// new Main().test();
// new Main().gen();
new Main().run();
// new Main().solve();
// long usedMemory = runtime.totalMemory() - runtime.freeMemory();
// System.err.printf("使用メモリ: %.2f MB%n", usedMemory / 1024.0 / 1024.0);
MyPrintWriter.getInstance().flush();
}
final long mod = 998244353;
@Override
public void run() {
FastScanner sc = FastScanner.getInstance();
MyPrintWriter pw = MyPrintWriter.getInstance();
int N = sc.nextInt();
long[][] A = sc.nextLongs(N, N);
long[][] B = sc.nextLongs(N, N);
long[] ans = f(B, A);
ans = Arrays.copyOf(ans, N + 1);
pw.println(ans, "\n");
}
/**
* det(Ax+B)
*
* @param A
* @param B
* @return */
long[] f(long[][] A, long[][] B) {
int N = A.length;
long[][] C = new long[N][2 * N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
C[i][j] = A[i][j];
C[i][j + N] = B[i][j];
}
}
long d = 1;
int offset = 0;
for (int i = 0; i < N; ++i) {
if (offset == (N + 1)) {
// 特性多項式の次数は高々N。N+1次の特性多項式は存在しないので0を返す。
return new long[]{ 0 };
}
{
int j = i;
while ((j < C.length) && (C[j][i] == 0)) {
++j;
}
if (j == C.length) {
for (int k = 0; k < i; k++) {
if (C[k][i] == 0) {
continue;
}
long c = mod - C[k][i];
for (int l = 0; l < N; l++) {
C[l][i] = (C[l][i] + (c * C[l][k])) % mod;
C[l][i + N] = (C[l][i + N] + (c * C[l][k + N])) % mod;
}
}
ArrayUtils.swapColumns(i, i + N, C);
offset++;
i--;
continue;
}
if (i != j) {
d = mod - d;
ArrayUtils.swap(C[i], C[j]);
}
}
d = (d * C[i][i]) % mod;
long invCii = MathUtils.modInv(C[i][i], mod);
for (int j = 0; j < C[i].length; ++j) {
C[i][j] = (C[i][j] * invCii) % mod;
}
for (int j = 0; j < C.length; ++j) {
if (i == j) {
continue;
}
if (C[j][i] == 0) {
continue;
}
long c = mod - C[j][i];
for (int k = 0; k < C[j].length; ++k) {
C[j][k] = (C[j][k] + (c * C[i][k])) % mod;
}
}
}
for (int i = 0; i < N; i++) {
C[i] = Arrays.copyOfRange(C[i], N, 2 * N);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (C[i][j] != 0) {
C[i][j] = mod - C[i][j];
}
}
}
long[] ret = Matrix.characteristicPolynomialOnFp(C, mod);
for (int i = 0; i < ret.length; i++) {
ret[i] = (d * ret[i]) % mod;
}
return Arrays.copyOfRange(ret, offset, ret.length);
}
}