結果
問題 | No.911 ラッキーソート |
ユーザー |
|
提出日時 | 2024-09-09 01:01:42 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 173 ms / 2,000 ms |
コード長 | 1,706 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 36,712 KB |
最終ジャッジ日時 | 2024-09-09 01:01:51 |
合計ジャッジ時間 | 8,750 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
# No.911 ラッキーソート# https://yukicoder.me/problems/no/911/editorial# 给定一个所有元素都不同的数组.# 你可以对数组进行任意一次操作:# 从[L, R]中选择一个数,所有数异或上这个数.# 问有多少种方案,使得数组变成严格递增.## n<=2e5.# 按位填,通过计算msb,发现四种情况:# 1.必须1# 2.必须0# 3.0和1都不可以# 4.0和1都可以from functools import lru_cacheimport syssys.setrecursionlimit(int(1e6))input = lambda: sys.stdin.readline().rstrip("\r\n")MOD = 998244353INF = int(4e18)if __name__ == "__main__":N, L, R = map(int, input().split())A = list(map(int, input().split()))status = [-1] * 64 # 0: 0, 1: 1, -1: 0 or 1def calc_bitwise_status() -> bool:for a, b in zip(A, A[1:]):msb = (a ^ b).bit_length() - 1if (a >> msb) & 1 == 0:if status[msb] == 1:return Falsestatus[msb] = 0else:if status[msb] == 0:return Falsestatus[msb] = 1return Trueif not calc_bitwise_status():print(0)exit()# 根据每个位选/不选,数位dp计算方案数@lru_cache(None)def dfs(v: int, bit: int) -> int:if v < 0:return 0if bit == 63:return 1s = status[bit]if s == 0:return dfs(v // 2, bit + 1)if s == 1:return dfs((v - 1) // 2, bit + 1)return dfs(v // 2, bit + 1) + dfs((v - 1) // 2, bit + 1)res1, res2 = dfs(R, 0), dfs(L - 1, 0)dfs.cache_clear()print(res1 - res2)