結果
問題 |
No.3231 2×2行列相似判定 〜hard〜
|
ユーザー |
![]() |
提出日時 | 2025-07-19 04:31:21 |
言語 | D (dmd 2.109.1) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 9,317 bytes |
コンパイル時間 | 2,637 ms |
コンパイル使用メモリ | 137,592 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-07-29 02:25:26 |
合計ジャッジ時間 | 4,380 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 37 |
ソースコード
import std.stdio, std.algorithm, std.array, std.conv, std.typecons; immutable p = 10L^^9 + 7; alias F = FiniteField!p; alias FP = Polynomial!(F); alias Mat = Matrix!FP; void main() { auto N = readln[0 .. $-1].to!uint; auto A = new Mat(N, N), B = new Mat(N, N); long[][] a, b; foreach (i; 0 .. N) a ~= readln.split.to!(long[]); foreach (i; 0 .. N) b ~= readln.split.to!(long[]); writeln(solve(a, b) ? "Yes" : "No"); } bool solve(long[][] a, long[][] b) { auto mat_a = char_mat(a), mat_b = char_mat(b); auto inv_fac_a = smith_form(mat_a), inv_fac_b = smith_form(mat_b); foreach (i; 0 .. a.length) { if (!inv_fac_a[i].equal(inv_fac_b[i])) return false; } return true; } Mat char_mat(long[][] a) { auto mat = new Mat(a.length, a.length); foreach (i, ar; a) foreach (j, val; ar) mat[i, j] = i == j ? new FP([F(-a[i][j]), F(1)]) : new FP([F(-a[i][j])]); return mat; } FP[] smith_form(Mat mat) { import std.algorithm; FP[] result; ulong n = 0; loop: while (n < min(mat.size1, mat.size2)) { /* yield the form * 0 0 ... 0 * * ... . 0 * * ... */ bool flag; do { flag = false; // bring the nonzero, minimal degree element to [n, n] ulong indi = n, indj = n; foreach (i; n .. mat.size1) foreach (j; n .. mat.size2) if ((!mat[i, j].is_zero && mat[i, j].deg < mat[indi, indj].deg) || mat[indi, indj].is_zero) indi = i, indj = j; // zero matrix if (mat[indi, indj].is_zero) { foreach (i; 0 .. min(mat.size1, mat.size2)) result ~= new FP([F(0)]); return result; } // swap to bring [indi, indj] to [n, n] mat.row_swap(n, indi), mat.col_swap(n, indj); // deal with [i, n] foreach (i; n+1 .. mat.size1) if (!mat[i, n].is_zero) mat.row_add(i, -mat[i, n]/mat[n, n], n), flag = true; // deal with [n, j] foreach (j; n+1 .. mat.size2) if (!mat[n, j].is_zero) mat.col_add(j, -mat[n, j]/mat[n, n], n), flag = true; } while (flag); foreach (i; n+1 .. mat.size1) foreach (j; n+1 .. mat.size2) { auto r = mat[i, j] % mat[n, n]; if (!r.is_zero) { mat[n, j] = new FP(mat[n, n].coeffs); mat[i, n] = r - mat[i, j]; mat[i, j] = r; continue loop; } } result ~= mat[n, n] / mat[n, n].coeffs[$-1]; ++n; } return result; } class Matrix(T) { ulong size1, size2; T[] entries; this (ulong size1, ulong size2) { this.size1 = size1; this.size2 = size2; this.entries.length = size1 * size2; } T opIndex(ulong i, ulong j) { assert (i < size1 && j < size2); return entries[i * size2 + j]; } T opIndexAssign(T val, ulong i, ulong j) { assert (i < size1 && j < size2); return entries[i * size2 + j] = val; } T opIndexOpAssign(string op)(T val, ulong i, ulong j) if (op == "+" || op == "-" || op == "*") { assert (i < size1 && j < size2); return mixin("entries[i * size2 + j] "~op~"= val"); } void row_mul(ulong i, T c) { foreach (j; 0 .. size2) this[i, j] *= c; } void col_mul(ulong j, T c) { foreach (i; 0 .. size1) this[i, j] *= c; } // change i-th row void row_add(ulong i, T c, ulong i2) { foreach (j; 0 .. size2) this[i, j] += (c * this[i2, j]); } // change j-th column void col_add(ulong j, T c, ulong j2) { foreach (i; 0 .. size1) this[i, j] += (c * this[i, j2]); } void row_swap(ulong i1, ulong i2) { foreach (j; 0 .. size2) { auto tmp = this[i2, j]; this[i2, j] = this[i1, j]; this[i1, j] = tmp; } } void col_swap(ulong j1, ulong j2) { foreach (i; 0 .. size1) { auto tmp = this[i, j2]; this[i, j2] = this[i, j1]; this[i, j1] = tmp; } } bool is_zero() @property { foreach (i; 0 .. size1) foreach (j; 0 .. size2) if (!this[i, j].is_zero) return false; return true; } void show(ulong n1=0, ulong n2=0) { foreach (i; n1 .. size1) { foreach (j; n2 .. size2) write(this[i, j], " "); writeln; } } } class Polynomial(T) { // c[0] + c[1] x + c[2] x^2 + ... T[] coeffs; this (T[] coeffs) { this.coeffs = coeffs; cut_zeros(); } void cut_zeros() { while (coeffs.length > 1 && coeffs[$-1] == 0) coeffs.length --; } ulong deg() @property { cut_zeros(); assert(coeffs.length > 0); return coeffs.length - 1; } Polynomial!T opUnary(string op: "+")() { return this; } Polynomial!T opUnary(string op: "-")() { this.cut_zeros(); T[] cs; foreach (c; coeffs) cs ~= -c; return new Polynomial!T(cs); } Polynomial!T opBinary(string op)(T rhs) { return this.opBinary!op(new Polynomial!T([rhs])); } Polynomial!T opBinary(string op)(Polynomial!T rhs) { import std.algorithm, std.array; T[] cs; this.cut_zeros(); rhs.cut_zeros(); static if (op == "+" || op == "-") { cs.length = max(this.coeffs.length, rhs.coeffs.length); foreach (i; 0 .. this.coeffs.length) { cs[i] = this.coeffs[i]; } foreach (i; 0 .. rhs.coeffs.length) { mixin("cs[i] " ~ op ~ "= rhs.coeffs[i];"); } } else if (op == "*") { cs.length = this.coeffs.length + rhs.coeffs.length; foreach (i; 0 .. this.coeffs.length) foreach (j; 0 .. rhs.coeffs.length) { cs[i + j] += this.coeffs[i] * rhs.coeffs[j]; } } else if (op == "/" || op == "%") { assert(rhs.coeffs.length > 1 || rhs.coeffs[0] != T(0)); // special cases if (this.coeffs.length < rhs.coeffs.length) return op == "/" ? new Polynomial([T(0)]) : new Polynomial(this.coeffs.dup); if (rhs.coeffs.length == 1) return op == "/" ? new Polynomial(this.coeffs[].map!(x => x / rhs.coeffs[0]).array) : new Polynomial([T(0)]); auto lhs_coeffs = this.coeffs.dup; foreach(i; 0 .. this.coeffs.length - rhs.coeffs.length + 1) { cs ~= lhs_coeffs[$-1-i] / rhs.coeffs[$-1]; foreach (j; 0 .. rhs.coeffs.length) lhs_coeffs[$-1-i-j] -= cs[i] * rhs.coeffs[$-1-j]; } cs = cs.reverse.array; if (op == "%") { cs = lhs_coeffs; cs.length = rhs.coeffs.length - 1; } } else assert(0); return new Polynomial(cs); } Polynomial!T opOpAssign(string op)(Polynomial!T rhs) { this.coeffs = this.opBinary!op(rhs).coeffs; cut_zeros(); return this; } Polynomial!T opOpAssign(string op)(T rhs) { this.coeffs = this.opBinary!op(rhs).coeffs; cut_zeros(); return this; } bool equal(Polynomial!T rhs) { cut_zeros(), rhs.cut_zeros(); return this.coeffs.equal(rhs.coeffs); } bool equal(T rhs) { cut_zeros(); return this.coeffs.length == 1 && this.coeffs[0] == rhs; } bool is_zero() @property { cut_zeros(); return this.coeffs.length == 1 && this.coeffs[0] == T(0); } override string toString() { string result = "["; foreach_reverse (c; coeffs) { result ~= c.toString() ~ ", "; } return result[0 .. $-2] ~ "]"; } } // the struct of finite fields with p elements // p must be a prime number struct FiniteField(long p) if (p > 1) { ulong n; this(long n) { if (n < 0) this.n = n%p + p; else this.n = n%p; } FiniteField!p opUnary(string op: "+")() { return this; } FiniteField!p opUnary(string op: "-")() { return FiniteField!p(-n); } FiniteField!p opBinary(string op)(long rhs) { static if (op == "^^") { if (rhs < 0) { return this.inv() ^^ rhs; } auto result = FiniteField!p(1); auto i = 0, pow_2_i = this; // pow_2_i = n^{2^i} rhs %= (p-1); while (rhs > 0) { if (rhs % 2 == 1) { result = result * pow_2_i; } rhs >>= 1; i++; pow_2_i = pow_2_i * pow_2_i; } return result; } else { return this.opBinary!op(FiniteField!p(rhs)); } } FiniteField!p opBinary(string op)(FiniteField!p rhs) { auto result = this; static if (op == "+") { result.n = (result.n + rhs.n) % p; } else if (op == "-") { result.n = (result.n + p - rhs.n) % p; } else if (op == "*") { result.n = (result.n * rhs.n) % p; } else if (op == "/") { assert (rhs.n != 0); result.n = (result.n * rhs.inv().n) % p; } else assert(0); return result; } FiniteField!p opOpAssign(string op)(long rhs) { return this = this.opBinary!op(rhs); } FiniteField!p opOpAssign(string op)(FiniteField!p rhs) { return this = this.opBinary!op(rhs); } bool opEquals(FiniteField!p rhs) { return (this.n + p - rhs.n) % p == 0; } bool opEquals(long rhs) { return (this.n + p - rhs) % p == 0; } FiniteField!p inv() { assert (this.n != 0); return this ^^ (p-2); } string toString() { import std.conv: to; return n.to!string; } }