結果

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

ソースコード

diff #
raw source code 

MOD = 998244353

def main():
    import sys
    from functools import lru_cache
    
    data = sys.stdin.read().split()
    if not data:
        return
    N = int(data[0])
    
    # ?????f(n)
    memo_f = {0: 0, 1: 1}
    
    def f(n):
        if n in memo_f:
            return memo_f[n]
        if n % 2 == 0:
            res = f(n // 2) + 1
        else:
            res = min(f((n - 1) // 2), f((n + 1) // 2)) + 2
        memo_f[n] = res
        return res
    
    # ???S(n)??
    memo_S = {0: 0, 1: 1}
    
    def S(n):
        if n in memo_S:
            return memo_S[n]
        
        if n % 2 == 0:
            k = n // 2
            # ????n????????
            # ?????sum(f(2i)) = sum(f(i) + 1) = S(k) + k
            # ??????????
            odd_sum = 0
            for i in range(1, n, 2):
                odd_sum += f(i)
            res = (S(k) + k + odd_sum) % MOD
        else:
            res = (S(n - 1) + f(n)) % MOD
        
        memo_S[n] = res
        return res
    
    result = S(N) % MOD
    print(result)

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