結果

問題 No.3432 popcount & sum (Hard)
コンテスト
ユーザー titia
提出日時 2026-01-24 05:43:18
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 808 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 309 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 83,536 KB
最終ジャッジ日時 2026-01-24 05:45:02
合計ジャッジ時間 103,741 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

mod=998244353
from functools import lru_cache
@lru_cache(maxsize=None)
def calc(keta,n,i):
    DP=[0]*63

    if n==0:
        if keta>=i:
            return DP
        DP[0]=1

        return DP

    if keta==i:
        DP2=calc(keta,(n-1)//2,i+1)

        for j in range(1,63):
            DP[j]=DP2[j-1]

        return DP

    else:
        DP2=calc(keta,n//2,i+1)
        DP3=calc(keta,(n-1)//2,i+1)

        for j in range(63):
            DP[j]=DP2[j]
            if j>=1:
                DP[j]+=DP3[j-1]
            DP[j]%=mod

        return DP


ANS=0
n=int(input())
for i in range(63):
    DP=calc(i,n,0)
    P=pow(2,i,mod)

    for j in range(63):
        x=DP[j]
        ANS+=P*(x*(x+1)//2)
        ANS%=mod

    #print(DP)

print(ANS%mod)
0