結果

問題 No.1829 Möbius Tunnelling
コンテスト
ユーザー cologne
提出日時 2026-03-13 15:48:38
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 1,886 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 515 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 66,872 KB
最終ジャッジ日時 2026-03-13 15:48:42
合計ジャッジ時間 3,523 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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())
    a, b, c = map(int1, input().split())
    c += n

    def rot(x):
        nonlocal a, b, c
        a, b, c = (a + x) % (2 * n), (b + x) % (2 * n), (c + x) % (2 * n)
        return a < n and c < n and b >= n

    for x in [-a, n - 1, -b + n, n - 1, -c, n - 1]:
        if rot(x):
            return 'Yes'

    return 'No'


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