結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
|
提出日時 | 2021-10-08 23:26:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 803 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 61,184 KB |
最終ジャッジ日時 | 2024-07-23 07:28:55 |
合計ジャッジ時間 | 3,827 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
C, N, M = map(int, input().split())MOD = 10 ** 9 + 7iC = pow(C, MOD - 2, MOD)"""pypy用行列累乗ライブラリは https://github.com/fujihiraryo/alogorithm-python/blob/master/integer/matrix.py から拝借しています。"""def product(a, b, p=MOD):n = len(a)c = [[0] * n for i in range(n)]for i in range(n):for j in range(n):c[i][j] = sum([a[i][k] * b[k][j] for k in range(n)]) % preturn cdef matpow(a, k, p=MOD):if k == 1:return aif k % 2 == 0:b = matpow(a, k // 2)return product(b, b, p=p)return product(a, matpow(a, k - 1), p=p)A = [[iC, 0, 0, 1 - iC],[0, iC, iC, 1 - 2 * iC],[1, 0, 0, 0],[0, 1, 0, 0]]tmp = matpow(A, N)[0][0]ans = (1 - pow(1 - tmp, M, MOD)) % MODprint(ans)