DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Maximize AND

返回题目

题解

SSS의 모든 1인 비트가 어떤 AiA_iAi​에도 모두 포함되는지를 빠르게 판정할 수 있으면 된다.

크기 2202^{20}220의 불 배열 cancancan을 만든다. 처음에는 등장한 값에 대해 can[Ai]=truecan[A_i]=\mathrm{true}can[Ai​]=true로 둔다. 그 다음 각 비트 b=0,1,⋯ ,19b=0,1,\cdots,19b=0,1,⋯,19에 대해, bbb번 비트가 0인 모든 마스크 SSS에 다음 전이를 적용한다.

can[S]←can[S]∨can[S∣2b]can[S] \leftarrow can[S] \lor can[S \mathbin{|} 2^b]can[S]←can[S]∨can[S∣2b]

이 SOS DP가 끝나면 can[S]can[S]can[S]는 어떤 AiA_iAi​가 SSS의 모든 1인 비트를 포함할 때, 즉 (Ai&S)=S(A_i \mathbin{\&} S)=S(인 가 존재할 때 정확히 참이다.

이제 쿼리 XXX를 처리한다. 답을 ans=0ans=0ans=0으로 시작하고 비트 191919부터 000까지 내려간다. 현재 비트가 XXX에서 1이고 can[ans∣가 참이라면 그 비트를 에 추가한다. 높은 비트부터 가능한 한 1로 만들었으므로 마지막 가 최댓값이다.

한 테스트 케이스의 전처리는 O(N+20⋅220)O(N+20\cdot 2^{20})O(N+20⋅220), 모든 쿼리는 O(20Q)O(20Q)O(20Q)에 처리된다. 메모리 사용량은 O(220)O(2^{20})이다.

증명

SOS DP 이후 can[S]can[S]can[S]가 참이라는 것은 정확히 SSS의 모든 1인 비트를 포함하는 AiA_iAi​가 하나 이상 존재한다는 뜻이다. 따라서 쿼리 처리 중 can[ans∣2b가 참이면, 지금까지 선택한 모든 비트와 번 비트를 동시에 포함하는 하나의 가 존재한다.

Solution written by GPT5.6

Ai​
&
S)=
S
iii
2b]can[ans \mathbin{|} 2^b]
can[ans∣2b]
ansansans
ansansans
O(220)
]can[ans \mathbin{|} 2^b]
can[ans∣2b]
bbb
AiA_iAi​

비트를 높은 곳부터 본다고 하자. 현재 비트 bbb를 1로 만들 수 있다면, 그 비트를 0으로 둔 어떤 결과보다 값이 크다. 더 낮은 모든 비트의 합은 2b−12^b-12b−1 이하이기 때문이다. 그러므로 가능한 경우에는 반드시 bbb번 비트를 1로 선택하는 것이 최적이다.

이 선택을 각 비트에 반복하면, 매 단계에서 지금까지 정한 더 높은 비트들을 유지하면서 만들 수 있는 최댓값의 접두부를 얻는다. 마지막에는 어떤 AiA_iAi​와의 AND로 실제 달성 가능한 값 중 가장 큰 값이 남으므로 알고리즘은 정답을 출력한다.