結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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;
    }
}
0