結果
| 問題 |
No.3231 2×2行列相似判定 〜hard〜
|
| コンテスト | |
| ユーザー |
 ジュ・ビオレ・グレイス
|
| 提出日時 | 2025-07-27 16:43:58 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 9,322 bytes |
| コンパイル時間 | 1,474 ms |
| コンパイル使用メモリ | 135,028 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-29 02:25:31 |
| 合計ジャッジ時間 | 2,659 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 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 = 2; //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;
}
}