結果

問題 No.1073 無限すごろく
ユーザー LyricalMaestro
提出日時 2025-07-19 18:08:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 1,081 bytes
コンパイル時間 486 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 63,172 KB
最終ジャッジ日時 2025-07-19 18:08:46
合計ジャッジ時間 3,706 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/286

MOD = 10 ** 9 + 7

def prod_vec(matrix, vector):
    new_vector = [0 for _ in range(6)]
    for i in range(6):
        for j in range(6):
            new_vector[i] += (matrix[i][j] * vector[j])% MOD
            new_vector[i] %= MOD
    return new_vector

def prod(left, right):
    new_matrix = [[0] * 6 for _ in range(6)]
    for i in range(6):
        for j in range(6):
            for k in range(6):
                new_matrix[i][j] += (left[i][k] * right[k][j]) % MOD
                new_matrix[i][j] %= MOD
    return new_matrix


def main():
    N = int(input())

    p = pow(6, MOD - 2, MOD)

    matrix = [
        [p, 1,  0, 0, 0, 0],
        [p, 0,  1, 0, 0, 0],
        [p, 0,  0, 1, 0, 0],
        [p, 0,  0, 0, 1, 0],
        [p, 0,  0, 0, 0, 1],
        [p, 0,  0, 0, 0, 0]
    ]

    vector = [1, 0, 0, 0, 0, 0]
    while N > 0:
        if N % 2 == 1:
            vector = prod_vec(matrix, vector)
        
        matrix = prod(matrix, matrix)
        N //= 2
    print(vector[0])





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