結果

問題 No.950 行列累乗
ユーザー toyuzukotoyuzuko
提出日時 2020-07-26 18:11:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 6,883 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 94,136 KB
最終ジャッジ日時 2024-06-28 19:14:55
合計ジャッジ時間 11,395 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 210 ms
87,848 KB
testcase_01 AC 219 ms
87,496 KB
testcase_02 AC 41 ms
54,016 KB
testcase_03 AC 57 ms
65,664 KB
testcase_04 AC 40 ms
53,888 KB
testcase_05 AC 74 ms
72,704 KB
testcase_06 AC 68 ms
69,888 KB
testcase_07 AC 57 ms
65,664 KB
testcase_08 WA -
testcase_09 AC 61 ms
67,328 KB
testcase_10 AC 58 ms
66,048 KB
testcase_11 AC 55 ms
66,048 KB
testcase_12 AC 58 ms
66,944 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 56 ms
65,920 KB
testcase_16 WA -
testcase_17 AC 49 ms
63,104 KB
testcase_18 AC 65 ms
69,760 KB
testcase_19 AC 50 ms
63,360 KB
testcase_20 AC 51 ms
63,488 KB
testcase_21 AC 266 ms
91,820 KB
testcase_22 WA -
testcase_23 AC 207 ms
88,492 KB
testcase_24 AC 218 ms
86,568 KB
testcase_25 AC 187 ms
85,288 KB
testcase_26 AC 210 ms
89,392 KB
testcase_27 AC 217 ms
88,104 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 223 ms
88,492 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 229 ms
88,108 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 198 ms
85,552 KB
testcase_37 AC 193 ms
88,232 KB
testcase_38 AC 205 ms
88,620 KB
testcase_39 AC 204 ms
85,796 KB
testcase_40 AC 216 ms
92,464 KB
testcase_41 AC 217 ms
92,712 KB
testcase_42 AC 267 ms
92,464 KB
testcase_43 WA -
testcase_44 WA -
testcase_45 AC 256 ms
92,716 KB
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 AC 259 ms
92,840 KB
testcase_53 AC 260 ms
92,972 KB
testcase_54 AC 39 ms
54,144 KB
testcase_55 AC 41 ms
54,016 KB
testcase_56 AC 230 ms
94,136 KB
testcase_57 AC 39 ms
54,272 KB
testcase_58 WA -
testcase_59 AC 40 ms
53,504 KB
testcase_60 AC 265 ms
92,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 + 100)
    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))
0