結果
問題 | No.1968 Distance |
ユーザー |
![]() |
提出日時 | 2022-06-03 23:06:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,268 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,664 KB |
実行使用メモリ | 61,232 KB |
最終ジャッジ日時 | 2024-09-21 03:13:49 |
合計ジャッジ時間 | 2,595 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
mod = 998244353n = int(input())if n == 0:print(748683265)exit()ans = 0for i in range(1, 60):# 1/(2**i+1) → 1/(2**(i-1)+1)mode = 1button = ikoml = 1komr = 1now = 0while True:if mode:if now + komr >= n:button -= 1komr *= 2breakbutton -= 1now += komrkomr *= 2else:if now + koml >= n:koml *= 2breaknow += komlkoml *= 2if button <= 0:mode ^= 1if button > 0:mode = 0#print(button, koml, komr)if mode:#(1-x)/komrを積分せよ.#[1/komr x - 1/2 1/komr^2 x^2]#print(2)ans -= pow(2, mod-2, mod)*(pow((pow(2, i-1, mod)+1)*(pow(2, i-1, mod)+1), mod-2, mod)-pow((pow(2, i, mod)+1)*(pow(2, i, mod)+1), mod-2, mod))*pow(komr, mod-2, mod)%modans %= modans += pow(komr, mod-2, mod) * (pow(pow(2, i-1, mod)+1, mod-2, mod) - pow(pow(2, i, mod)+1, mod-2, mod)) % modans %= modelse:#x/komlを積分せよ.#[1/2 1/komr^2 x^2]ans += pow(2, mod-2, mod) * (pow((pow(2, i-1, mod)+1)*(pow(2, i-1, mod)+1), mod-2, mod) - pow((pow(2, i, mod)+1)*(pow(2, i, mod)+1), mod-2,mod)) * pow(koml, mod-2, mod) % modans %= mod#print(ans)ans += pow(2, mod-2, mod) * pow((pow(2, 59, mod)+1)*(pow(2, 59, mod)+1), mod-2, mod) % modans %= modprint(2 * ans % mod)