結果
| 問題 |
No.950 行列累乗
|
| コンテスト | |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2020-07-26 18:14:50 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,884 bytes |
| コンパイル時間 | 82 ms |
| コンパイル使用メモリ | 13,696 KB |
| 実行使用メモリ | 25,820 KB |
| 最終ジャッジ日時 | 2024-06-28 19:15:24 |
| 合計ジャッジ時間 | 23,419 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 39 WA * 18 |
ソースコード
class SquareMatrix():
def __init__(self, n, mod=1000000007):
self.n = n
self.mat = [[0 for j in range(n)] for i in range(n)]
self.mod = mod
@staticmethod
def id(n, mod=1000000007):
res = SquareMatrix(n, mod)
for i in range(n):
res.mat[i][i] = 1
return res
@staticmethod
def modinv(n, mod):
assert n % mod != 0
c0, c1 = n, mod
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1:
a0, a1 = a1, a0 - c0 // c1 * a1
b0, b1 = b1, b0 - c0 // c1 * b1
c0, c1 = c1, c0 % c1
return a0 % mod
def set(self, arr):
for i in range(self.n):
for j in range(self.n):
self.mat[i][j] = arr[i][j] % self.mod
def operate(self, vec):
assert len(vec) == self.n
res = [0 for _ in range(self.n)]
for i in range(self.n):
for j in range(self.n):
res[i] += self.mat[i][j] * vec[j]
res[i] %= self.mod
return res
def add(self, other):
assert other.n == self.n
res = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
res.mat[i][j] = self.mat[i][j] + other.mat[i][j]
res.mat[i][j] %= self.mod
return res
def subtract(self, other):
assert other.n == self.n
res = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
res.mat[i][j] = self.mat[i][j] - other.mat[i][j]
res.mat[i][j] %= self.mod
return res
def times(self, k):
res = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
res.mat[i][j] = self.mat[i][j] * k
res.mat[i][j] %= self.mod
return res
def multiply(self, other):
assert self.n == other.n
res = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
for k in range(self.n):
res.mat[i][j] += self.mat[i][k] * other.mat[k][j]
res.mat[i][j] %= self.mod
return res
def power(self, k):
tmp = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
tmp.mat[i][j] = self.mat[i][j]
res = SquareMatrix.id(self.n, self.mod)
while k:
if k & 1:
res = res.multiply(tmp)
tmp = tmp.multiply(tmp)
k >>= 1
return res
def trace(self):
res = 0
for i in range(self.n):
res += self.mat[i][i]
res %= self.mod
return res
def determinant(self):
res = 1
tmp = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
tmp.mat[i][j] = self.mat[i][j]
for j in range(self.n):
if tmp.mat[j][j] == 0:
for i in range(j + 1, self.n):
if tmp.mat[i][j] != 0:
idx = i
break
else:
return 0
for k in range(self.n):
tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]
res *= -1
inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)
for i in range(j + 1, self.n):
c = -inv * tmp.mat[i][j] % self.mod
for k in range(self.n):
tmp.mat[i][k] += c * tmp.mat[j][k]
tmp.mat[i][k] %= self.mod
for i in range(self.n):
res *= tmp.mat[i][i]
res %= self.mod
return res
def transpose(self):
res = SquareMatrix(self.n, self.mod)
for i in range(self.n):
for j in range(self.n):
res.mat[i][j] = self.mat[j][i]
return res
def inverse(self): #self.determinant() != 0
res = SquareMatrix.id(self.n, self.mod)
tmp = SquareMatrix(self.n, self.mod)
sgn = 1
for i in range(self.n):
for j in range(self.n):
tmp.mat[i][j] = self.mat[i][j]
for j in range(self.n):
if tmp.mat[j][j] == 0:
for i in range(j + 1, self.n):
if tmp.mat[i][j] != 0:
idx = i
break
else:
return 0
for k in range(self.n):
tmp.mat[j][k], tmp.mat[idx][k] = tmp.mat[idx][k], tmp.mat[j][k]
res.mat[j][k], res.mat[idx][k] = res.mat[idx][k], res.mat[j][k]
inv = SquareMatrix.modinv(tmp.mat[j][j], self.mod)
for k in range(self.n):
tmp.mat[j][k] *= inv
tmp.mat[j][k] %= self.mod
res.mat[j][k] *= inv
res.mat[j][k] %= self.mod
for i in range(self.n):
c = tmp.mat[i][j]
for k in range(self.n):
if i == j:
continue
tmp.mat[i][k] -= tmp.mat[j][k] * c
tmp.mat[i][k] %= self.mod
res.mat[i][k] -= res.mat[j][k] * c
res.mat[i][k] %= self.mod
return res
def linear_equations(self, vec):
return self.inverse().operate(vec)
def print(self):
print(*self.mat, sep='\n')
def is_same(A, B):
if A.n != B.n:
return False
n = A.n
for i in range(n):
for j in range(n):
if A.mat[i][j] != B.mat[i][j]:
return False
return True
from itertools import chain
def discrete_logarithm(x, y, mod): #x**k % mod == y
if is_same(y, SquareMatrix.id(2, mod)): return -1
if is_same(x, SquareMatrix(2, mod)) and is_same(y, SquareMatrix(2, mod)): return 1
sqrt_mod = int(mod**0.5 + 1000)
power_x = {}
p = SquareMatrix.id(2, mod)
for i in range(sqrt_mod):
if is_same(p, y):
return i #x**i % mod == y
tmp = p.multiply(y)
tmp = tuple(chain.from_iterable(tmp.mat))
power_x[tmp] = i
p = p.multiply(x)
z = x.power(sqrt_mod)
g = SquareMatrix.id(2, mod)
for i in range(1, sqrt_mod + 3):
g = g.multiply(z)
tmp = tuple(chain.from_iterable(g.mat))
if tmp in power_x:
res = i * sqrt_mod - power_x[tmp]
if is_same(x.power(res), y):
return res
return -1
MOD = int(input())
a = [tuple(map(int, input().split())) for _ in range(2)]
b = [tuple(map(int, input().split())) for _ in range(2)]
A = SquareMatrix(2, MOD)
B = SquareMatrix(2, MOD)
A.set(a)
B.set(b)
print(discrete_logarithm(A, B, MOD))