結果

問題 No.737 PopCount
ユーザー lam6er
提出日時 2025-03-20 19:00:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 176 ms / 1,000 ms
コード長 1,426 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 79,468 KB
最終ジャッジ日時 2025-03-20 19:01:26
合計ジャッジ時間 2,921 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

MOD = 10**9 + 7

def main():
    N = int(sys.stdin.readline())
    bits = list(map(int, bin(N)[2:]))  # Convert N to binary, then to a list of digits
    m = len(bits)
    total = 0

    for k in range(1, m + 1):
        # Calculate sum of numbers with exactly k ones in binary
        sum_k = 0
        cnt_k = 0

        @lru_cache(maxsize=None)
        def dp(pos, count, tight):
            nonlocal bits, k, m
            rem = m - pos
            required = k - count
            if required < 0 or required > rem:
                return (0, 0)
            if pos == m:
                return (0, 1) if required == 0 else (0, 0)
            max_bit = bits[pos] if tight else 1
            res_sum = 0
            res_cnt = 0
            for bit in range(0, max_bit + 1):
                new_tight = tight and (bit == max_bit)
                new_count = count + (bit == 1)
                s, c = dp(pos + 1, new_count, new_tight)
                w = pow(2, (m - 1 - pos), MOD)
                contrib = (bit * w) % MOD
                contrib = (contrib * c) % MOD
                res_sum = (res_sum + s + contrib) % MOD
                res_cnt = (res_cnt + c) % MOD
            return (res_sum % MOD, res_cnt % MOD)

        s, c = dp(0, 0, True)
        sum_k = s % MOD
        total = (total + sum_k * k) % MOD

    print(total % MOD)

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