結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
![]() |
提出日時 | 2021-10-30 00:32:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,014 bytes |
コンパイル時間 | 455 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 62,384 KB |
最終ジャッジ日時 | 2024-10-07 13:14:05 |
合計ジャッジ時間 | 3,700 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
def powmod(n,pow,mod):val = 1while pow > 0:if pow & 1:val = (val * n) % modpow = pow >> 1n = (n * n) % modreturn valdef matdot(a,b,mod):matsize = len(a)val = [[0 for i in range(matsize)] for j in range(matsize)]for i in range(matsize):for j in range(matsize):for k in range(matsize):val[i][j] = (val[i][j] + a[i][k] * b[k][j]) % modreturn valdef powmodmat(n,pow,mod):matsize = len(n)val = [[0 for i in range(matsize)] for j in range(matsize)]for i in range(matsize):val[i][i] = 1while pow > 0:if pow & 1:val = matdot(val, n, mod)pow = pow >> 1n = matdot(n, n, mod)return valc, n, m = map(int, input().split())p = 10**9+7inv = powmod(c,p-2,p)mat = [[inv,0,0,inv*(c-1)%p],[0,inv,inv,inv*(c-2)%p],[1,0,0,0],[0,1,0,0]]kari = powmodmat(mat,n,p)a = kari[0][0]ans = (1 - powmod((1-a)%p,m,p)) % pprint("{}".format(ans))