結果
問題 | No.1879 How many matchings? |
ユーザー |
|
提出日時 | 2022-03-18 23:55:17 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 734 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 52,864 KB |
最終ジャッジ日時 | 2024-10-03 10:13:40 |
合計ジャッジ時間 | 1,509 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 WA * 9 |
ソースコード
def dot(aa, bb):h = len(aa)w = len(bb[0])res = [[0]*w for _ in range(h)]for i, row in enumerate(aa):for j, col in enumerate(zip(*bb)):v = 0# for a, b in zip(row, col): v += a*b# res[i][j] = v%mdfor a, b in zip(row, col): v += a*b%mdres[i][j] = v%mdreturn resdef matpow(mat, e):n = len(mat)res = [[1 if i == j else 0 for j in range(n)] for i in range(n)]while e:if e & 1: res = dot(res, mat)mat = dot(mat, mat)e >>= 1return resmd = 10 ** 9 + 7N = int(input())A = [[0,1],[1,1]]if N % 2 == 0:powA = matpow(A,N//2)B = [[1],[1]]ans = dot(powA,B)print(ans[0][0])