#507329 (Python3) No.891 隣接3項間の漸化式

提出ソース

結果

問題	No.891 隣接3項間の漸化式
ユーザー	toyuzuko
提出日時	2020-07-05 16:50:17
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	34 ms / 2,000 ms
コード長	5,802 bytes
コンパイル時間	85 ms
コンパイル使用メモリ	13,440 KB
実行使用メモリ	11,520 KB
最終ジャッジ日時	2024-09-22 14:21:51
合計ジャッジ時間	2,569 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	33 ms 11,392 KB
testcase_01	AC	32 ms 11,392 KB
testcase_02	AC	32 ms 11,392 KB
testcase_03	AC	34 ms 11,392 KB
testcase_04	AC	33 ms 11,392 KB
testcase_05	AC	32 ms 11,392 KB
testcase_06	AC	32 ms 11,520 KB
testcase_07	AC	32 ms 11,392 KB
testcase_08	AC	33 ms 11,392 KB
testcase_09	AC	33 ms 11,520 KB
testcase_10	AC	33 ms 11,520 KB
testcase_11	AC	33 ms 11,392 KB
testcase_12	AC	33 ms 11,392 KB
testcase_13	AC	32 ms 11,392 KB
testcase_14	AC	32 ms 11,392 KB
testcase_15	AC	32 ms 11,392 KB
testcase_16	AC	32 ms 11,392 KB
testcase_17	AC	32 ms 11,392 KB
testcase_18	AC	32 ms 11,392 KB
testcase_19	AC	32 ms 11,392 KB
testcase_20	AC	32 ms 11,520 KB
testcase_21	AC	32 ms 11,392 KB
testcase_22	AC	31 ms 11,392 KB
testcase_23	AC	31 ms 11,520 KB
testcase_24	AC	32 ms 11,520 KB
testcase_25	AC	32 ms 11,392 KB
testcase_26	AC	32 ms 11,392 KB
testcase_27	AC	32 ms 11,520 KB
testcase_28	AC	33 ms 11,392 KB
testcase_29	AC	32 ms 11,392 KB
testcase_30	AC	32 ms 11,392 KB
testcase_31	AC	33 ms 11,520 KB
testcase_32	AC	33 ms 11,520 KB
testcase_33	AC	32 ms 11,520 KB
testcase_34	AC	32 ms 11,520 KB
testcase_35	AC	32 ms 11,520 KB
testcase_36	AC	32 ms 11,392 KB
testcase_37	AC	32 ms 11,520 KB
testcase_38	AC	32 ms 11,520 KB
testcase_39	AC	32 ms 11,520 KB
testcase_40	AC	32 ms 11,520 KB
testcase_41	AC	32 ms 11,392 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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): #self.determinant != 0
        return self.inverse().operate(vec)

    def print(self):
        print(*self.mat, sep='\n')

A, B, N = map(int, input().split())

if N == 0:
    print(0)
elif N == 1:
    print(1)
else:
    M = SquareMatrix(2)
    M.set([[A, B], [1, 0]])
    P = M.power(N - 1)
    print(P.operate([1, 0])[0])

yukicoder

結果

テストケース

ソースコード