結果

問題 No.911 ラッキーソート
ユーザー lam6er
提出日時 2025-04-15 23:46:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 1,650 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 81,704 KB
実行使用メモリ 112,344 KB
最終ジャッジ日時 2025-04-15 23:49:09
合計ジャッジ時間 5,760 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, L, R = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    if N == 1:
        print(R - L + 1)
        return

    constraints = {}
    for i in range(N-1):
        a = A[i]
        b = A[i+1]
        c = a ^ b
        if c == 0:
            print(0)
            return
        k = c.bit_length() - 1
        a_bit = (a >> k) & 1
        if k in constraints:
            if constraints[k] != a_bit:
                print(0)
                return
        else:
            constraints[k] = a_bit

    mask = 0
    value = 0
    for k in constraints:
        mask |= (1 << k)
        value |= (constraints[k] << k)

    def count(X):
        if (value & mask) != value:
            return 0
        if X < value:
            return 0
        max_f = X - value
        free_mask = ~mask & ((1 << 61) - 1)

        s = format(max_f, '061b')
        n = 61

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(pos, tight):
            if pos == n:
                return 1
            res = 0
            current_bit = n - 1 - pos
            max_bit = int(s[pos]) if tight else 1
            for bit in [0, 1]:
                if bit > max_bit:
                    continue
                new_tight = tight and (bit == max_bit)
                if (free_mask & (1 << current_bit)) == 0:
                    if bit != 0:
                        continue
                res += dp(pos + 1, new_tight)
            return res

        return dp(0, True)

    ans = count(R) - count(L - 1)
    print(ans)

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