結果

問題 No.1853 Many Operations
コンテスト
ユーザー vjudge1
提出日時 2025-11-14 21:34:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,128 bytes
記録
コンパイル時間 233 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 63,044 KB
最終ジャッジ日時 2025-11-14 21:34:42
合計ジャッジ時間 2,760 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 3 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

def solve():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    N = int(data[0])
    
    if N == 0:
        print(0)
        return
    
    # ?N?????????
    bin_str = bin(N)[2:]
    n = len(bin_str)
    
    # ???DP
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dfs(pos, limit, has_started):
        if pos == n:
            # ????????????????1?f?0?????f??0?
            return (1, 0) if has_started else (0, 0)
        
        max_digit = 1 if not limit else int(bin_str[pos])
        total_count = 0
        total_sum = 0
        
        for digit in range(max_digit + 1):
            next_limit = limit and (digit == max_digit)
            next_has_started = has_started or (digit == 1)
            
            if not next_has_started:
                # ???????????????
                cnt, s = dfs(pos + 1, next_limit, next_has_started)
                total_count = (total_count + cnt) % MOD
                total_sum = (total_sum + s) % MOD
            else:
                # ???????????????
                cnt, s = dfs(pos + 1, next_limit, next_has_started)
                total_count = (total_count + cnt) % MOD
                
                # ???????
                # ???????????????????1?f(1)=1?
                # ?????????1????1?popcount??1?
                # ??????????????????????
                if not has_started and digit == 1:
                    # ???????????f(1)=1
                    total_sum = (total_sum + cnt + s) % MOD
                else:
                    # ????????????1???1?popcount?
                    # ??????????????????????
                    bit_contrib = 1 if digit == 1 else 0
                    length_contrib = 1  # ?????????????????
                    total_sum = (total_sum + cnt * (bit_contrib + length_contrib) + s) % MOD
        
        return total_count, total_sum
    
    # ???1?N?f(i)??
    # ??????DP?????0?N?f(i)???????f(0)=0
    count, result = dfs(0, True, False)
    
    # ?????DP???0???????1???????????
    print(result % MOD)

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