結果
問題 |
No.444 旨味の相乗効果
|
ユーザー |
![]() |
提出日時 | 2020-04-03 03:05:02 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 681 ms / 2,500 ms |
コード長 | 790 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 44,688 KB |
最終ジャッジ日時 | 2024-06-28 17:39:12 |
合計ジャッジ時間 | 15,060 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import numpy as np MOD = 10 ** 9 + 7 N, C, *A = map(int, read().split()) mat = np.zeros((N, N), np.int64) for i, x in enumerate(A): mat[i, : i + 1] = x mat.flags.writeable = False def mult(A, B): A1, A2 = np.divmod(A, 1 << 16) B1, B2 = np.divmod(B, 1 << 16) X, Y, Z = np.dot(A1, B1), np.dot(A2, B2), np.dot(A1 + A2, B1 + B2) C = (X % MOD) << 32 C += ((Z - X - Y) % MOD) << 16 C += Y return C % MOD def power(A, n): if n == 1: return A B = power(A, n // 2) B = mult(B, B) return mult(A, B) if n & 1 else B M = power(mat, C) answer = (M[:, 0].sum() - M.diagonal().sum()) % MOD print(answer)