結果

問題 No.1968 Distance
ユーザー shobonvipshobonvip
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

mod = 998244353
n = int(input())
if n == 0:
print(748683265)
exit()
ans = 0
for i in range(1, 60):
# 1/(2**i+1) → 1/(2**(i-1)+1)
mode = 1
button = i
koml = 1
komr = 1
now = 0
while True:
if mode:
if now + komr >= n:
button -= 1
komr *= 2
break
button -= 1
now += komr
komr *= 2
else:
if now + koml >= n:
koml *= 2
break
now += koml
koml *= 2
if button <= 0:
mode ^= 1
if 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)%mod
ans %= mod
ans += pow(komr, mod-2, mod) * (pow(pow(2, i-1, mod)+1, mod-2, mod) - pow(pow(2, i, mod)+1, mod-2, mod)) % mod
ans %= mod
else:
#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) % mod
ans %= mod
#print(ans)
ans += pow(2, mod-2, mod) * pow((pow(2, 59, mod)+1)*(pow(2, 59, mod)+1), mod-2, mod) % mod
ans %= mod
print(2 * ans % mod)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0