結果

問題 No.3431 popcount & sum (Easy)
コンテスト
ユーザー cologne
提出日時 2026-03-13 15:13:44
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,658 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 555 ms
コンパイル使用メモリ 85,300 KB
実行使用メモリ 68,480 KB
最終ジャッジ日時 2026-03-13 15:13:46
合計ジャッジ時間 1,532 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

from typing import List, Tuple


def int1(x: str, /): return int(x) - 1


def input(): return sys.stdin.readline().rstrip('\n')


def dbg(*args, **kwargs):
    print(*(repr(arg) for arg in args), *(f'{k}: {repr(v)}' for k, v in kwargs.items()), sep='; ', file=sys.stderr)


M = 998_244_353

memo = {}


# sum [0..a) [0..b) f(a, b); sum [0..a) [0..b) I{popcnt(a) = popcnt(b)}
# where from 2^k mark, and popcnt(a) - popcnt(b) = dp
# i.e. a <= 2^k
def solve(a, b, k, dp):
    if a == 0 or b == 0:
        return 0, 0
    if k == 0:
        return 0, 1 if dp == 0 else 0
    key = (a, b, k, dp)
    ret = memo.get(key)
    if ret is not None:
        return ret

    rs, rc = solve(min(a, 1 << (k - 1)), min(b, 1 << (k - 1)), k - 1, dp)

    if a > (1 << (k - 1)):
        cs, cc = solve(a - (1 << (k - 1)), min(b, 1 << (k - 1)), k - 1, dp + 1)
        rs += cs
        rc += cc

    if b > (1 << (k - 1)):
        cs, cc = solve(min(a, 1 << (k - 1)), b - (1 << (k - 1)), k - 1, dp - 1)
        rs += cs
        rc += cc

    if a > (1 << (k - 1)) and b > (1 << (k - 1)):
        cs, cc = solve(a - (1 << (k - 1)), b - (1 << (k - 1)), k - 1, dp)
        rs += cs + (cc << (k - 1))
        rc += cc

    ret = (rs % M, rc % M)

    memo[key] = ret
    return ret


def main():
    n = int(input())
    ret, _ = solve(n + 1, n + 1, 60, 0)
    return (ret + n * (n + 1) // 2) * pow(2, -1, M) % M


def _start():
    ret = main()

    if ret is not None:
        if isinstance(ret, List) or isinstance(ret, Tuple):
            print(*ret)
        else:
            print(ret)


if __name__ == '__main__':
    _start()
0