結果

問題 No.1073 無限すごろく
ユーザー lam6er
提出日時 2025-03-26 15:50:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 48 ms / 2,000 ms
コード長 1,934 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 62,376 KB
最終ジャッジ日時 2025-03-26 15:51:30
合計ジャッジ時間 2,975 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    n = int(sys.stdin.readline())
    inv6 = pow(6, MOD-2, MOD)
    
    # Precompute p[0] to p[5]
    p = [0] * 6
    p[0] = 1
    if n == 0:
        print(p[0])
        return
    
    for i in range(1, 6):
        s = 0
        for j in range(1, i + 1):
            s = (s + p[i - j]) % MOD
        p[i] = s * inv6 % MOD
    
    if n < 6:
        print(p[n])
        return
    
    # Define the transition matrix
    mat = [
        [inv6] * 6,
        [1, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 1, 0]
    ]
    
    # Initial vector is [p5, p4, p3, p2, p1, p0]
    initial_vector = [p[5], p[4], p[3], p[2], p[1], p[0]]
    power = n - 5
    
    # Function to multiply two matrices
    def multiply(a, b):
        res = [[0]*6 for _ in range(6)]
        for i in range(6):
            for k in range(6):
                if a[i][k] == 0:
                    continue
                for j in range(6):
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD
        return res
    
    # Function to multiply matrix and vector
    def multiply_mat_vec(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
    
    # Matrix exponentiation
    result_mat = [[0]*6 for _ in range(6)]
    for i in range(6):
        result_mat[i][i] = 1  # Identity matrix
    
    current_mat = [row[:] for row in mat]
    while power > 0:
        if power % 2 == 1:
            result_mat = multiply(result_mat, current_mat)
        current_mat = multiply(current_mat, current_mat)
        power //= 2
    
    # Multiply the resulting matrix with the initial vector
    final_vec = multiply_mat_vec(result_mat, initial_vector)
    print(final_vec[0])

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