結果

問題 No.1073 無限すごろく
ユーザー lam6er
提出日時 2025-03-20 21:08:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 2,044 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 61,996 KB
最終ジャッジ日時 2025-03-20 21:09:19
合計ジャッジ時間 2,421 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    N = int(input())
    
    if N == 0:
        print(1)
        return
    
    inv6 = pow(6, MOD-2, MOD)
    p = [0] * 6
    p[0] = 1 % MOD
    if N < 6:
        for i in range(1, N + 1):
            total = 0
            for k in range(1, 7):
                if i - k >= 0:
                    total = (total + p[i - k]) % MOD
            p[i] = (total * inv6) % MOD
        print(p[N])
        return
    
    # Compute p[0] to p[5]
    p = [0] * 6
    p[0] = 1 % MOD
    for i in range(1, 6):
        total = 0
        for k in range(1, 7):
            if i - k >= 0:
                total = (total + p[i - k]) % MOD
        p[i] = (total * inv6) % MOD
    
    def multiply_matrices(a, b):
        res = [[0] * 6 for _ in range(6)]
        for i in range(6):
            for j in range(6):
                for k in range(6):
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD
        return res
    
    def multiply_vector(mat, vec):
        res = [0] * 6
        for i in range(6):
            for j in range(6):
                res[i] = (res[i] + mat[i][j] * vec[j]) % MOD
        return res
    
    def matrix_pow(mat, power):
        result = [[0] * 6 for _ in range(6)]
        for i in range(6):
            result[i][i] = 1  # Identity matrix
        while power > 0:
            if power % 2 == 1:
                result = multiply_matrices(result, mat)
            mat = multiply_matrices(mat, mat)
            power //= 2
        return result
    
    # Create the transition matrix
    def create_matrix(inv6):
        mat = [[0] * 6 for _ in range(6)]
        for j in range(6):
            mat[0][j] = inv6
        for i in range(1, 6):
            mat[i][i-1] = 1
        return mat
    
    mat = create_matrix(inv6)
    exponent = N - 5
    mat_pow = matrix_pow(mat, exponent)
    
    initial_vector = [p[5], p[4], p[3], p[2], p[1], p[0]]
    
    final_vector = multiply_vector(mat_pow, initial_vector)
    print(final_vector[0])

if __name__ == "__main__":
    main()
0