結果

問題 No.1879 How many matchings?
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:46:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 779 bytes
コンパイル時間 235 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 52,096 KB
最終ジャッジ日時 2025-06-12 20:47:23
合計ジャッジ時間 1,599 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def fib(n, mod):
    if n == 0:
        return 0
    def multiply(a, b):
        return (
            (a[0]*b[0] + a[1]*b[2]) % mod,
            (a[0]*b[1] + a[1]*b[3]) % mod,
            (a[2]*b[0] + a[3]*b[2]) % mod,
            (a[2]*b[1] + a[3]*b[3]) % mod
        )
    
    def matrix_pow(mat, power):
        result = (1, 0, 0, 1)  # Identity matrix
        while power > 0:
            if power % 2 == 1:
                result = multiply(result, mat)
            mat = multiply(mat, mat)
            power //= 2
        return result
    
    mat = matrix_pow( (1, 1, 1, 0), n-1 )
    return mat[0]

n = int(input())
if n == 1:
    print(1)
elif n % 2 == 0:
    k = n // 2 + 1
    print(fib(k, MOD))
else:
    k = (n - 1) // 2 + 3
    print(fib(k, MOD))
0