結果

問題 No.1853 Many Operations
コンテスト
ユーザー vjudge1
提出日時 2025-11-14 21:27:54
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,377 bytes
記録
コンパイル時間 220 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 81,716 KB
最終ジャッジ日時 2025-11-14 21:28:09
合計ジャッジ時間 5,118 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 RE * 1
other AC * 3 RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

class Solver:
    def __init__(self):
        self.memo_f = {}
        self.memo_s = {}
        self.memo_u = {}

    def f(self, n):
        if n in self.memo_f:
            return self.memo_f[n]
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n % 2 == 0:
            res = self.f(n // 2) + 1
        else:
            res = min(self.f((n - 1) // 2) + 2, self.f((n + 1) // 2) + 2)
        self.memo_f[n] = res % MOD
        return self.memo_f[n]

    def u(self, m):
        if m in self.memo_u:
            return self.memo_u[m]
        if m <= 1:
            return 0
        res = self.u(m - 1) + min(self.f(m - 1), self.f(m))
        self.memo_u[m] = res % MOD
        return self.memo_u[m]

    def s(self, n):
        if n in self.memo_s:
            return self.memo_s[n]
        if n == 0:
            return 0
        if n == 1:
            return 1
        a = n // 2
        b = (n - 1) // 2
        part1 = 1 + a + 2 * b
        part2 = self.s(a)
        part3 = self.u(b + 1)
        res = part1 + part2 + part3
        self.memo_s[n] = res % MOD
        return self.memo_s[n]

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    N = int(data[0])
    solver = Solver()
    result = solver.s(N) % MOD
    print(result)

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