結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
![]() |
提出日時 | 2021-10-09 19:59:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 766 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 62,396 KB |
最終ジャッジ日時 | 2024-09-13 08:45:08 |
合計ジャッジ時間 | 3,531 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
C, N, M = map(int, input().split())MOD = 10**9+7A = [[0]*4 for _ in range(4)]inv = pow(C, MOD-2, MOD)A[0][2] = A[1][3] = 1A[2][1] = A[2][2] = A[3][3] = invA[3][0] = (C-1)*inv % MODA[3][1] = (C-2)*inv % MODdef multiple(X, Y):r = len(X)c = len(Y[0])n = len(Y)Z = [[0]*c for _ in range(r)]for i in range(r):for j in range(c):for k in range(n):Z[i][j] += X[i][k]*Y[k][j] % MODZ[i][j] %= MODreturn ZL = 30B = []B.append(A)for _ in range(L):B.append(multiple(B[-1], B[-1]))v = [[0] for _ in range(4)]v[0][0] = 1v[2][0] = invfor i in range(L):if (N >> i) & 1:v = multiple(B[i], v)p = (1-v[0][0]) % MODans = (1-pow(p, M, MOD)) % MODprint(ans)