結果

問題 No.3431 popcount & sum (Easy)
コンテスト
ユーザー hirayuu_yc
提出日時 2025-12-29 22:46:18
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 70 ms / 2,000 ms
コード長 1,170 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 154 ms
コンパイル使用メモリ 82,900 KB
実行使用メモリ 76,600 KB
最終ジャッジ日時 2026-01-11 13:05:34
合計ジャッジ時間 1,245 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD=998244353
n=int(input())
dp=[[[0,0] for i in range(4)] for i in range(125)]
dp[61][0]=[1,0]
for i in range(60):
    ndp=[[[0,0] for i in range(4)] for i in range(125)]
    x=(n>>(59-i))&1
    for j in range(125):
        for k in range(4):
            dp[j][k][0]%=MOD
            dp[j][k][1]%=MOD
            if dp[j][k]==[0,0]:
                continue
            t=[k//2,k%2]
            for l in range(4):
                s=[l//2,l%2]
                if t[0]==0 and s[0]>x:
                    continue
                if t[1]==0 and s[1]>x:
                    continue
                nxt=t[:]
                if t[0]==0 and s[0]<x:
                    nxt[0]=1
                if t[1]==0 and s[1]<x:
                    nxt[1]=1
                id=0
                if l==1:
                    id=-1
                if l==2:
                    id=1
                p=0
                if l==3:
                    p=1
                ndp[j+id][nxt[0]*2+nxt[1]][0]+=dp[j][k][0]
                ndp[j+id][nxt[0]*2+nxt[1]][1]+=dp[j][k][1]*2+p*dp[j][k][0]
    dp=ndp
ans=0
for i in range(4):
    ans+=dp[61][i][1]
ans+=n*(n+1)//2
print((ans*pow(2,-1,MOD))%MOD)
0