概要

GG の満たす性質をうまく利用しましょう.

問題原案:viral
改題:uni_kakurenbo

解説

任意の 22 非負整数 u,vu, v について u&v=uu \,\&\, v = u であることを uvu \subseteq v と書きます. (bit の集合を想像してください.uu で立っているビットはすべて vv でも立っています.)

また,「A[i]A[j]A[i] \subseteq A[j] のとき iji \to j の辺を張る」とありますが,記号の向きが逆で分かりづらいので「A[i]A[j]A[i] \subseteq A[j] のとき iji \gets j の辺を張る」とします.このとき次数が 00 となる頂点の個数を数えます.

また,「任意の 3 非負整数 u,v,wu, v, w について『(uvu \subseteq v かつ vwv \subseteq w) ならば uwu \subseteq w』」であることは容易にわかります.(これを形式的に「推移律が満たされている」とも言います.)

また,「任意の相異なる 2 非負整数 u,vu, v について『uvu \subseteq v ならば uvu \subseteq v ではない』」ことも当然成り立ちます.(これを形式的に「反対称律が満たされている」ともいいます.)

以上のことを踏まえると,AA は distinct な (相異なる) ので,グラフ GG は 有向非循環 (DAG) になります.(これを形式的に「\subseteq が非負整数全体の集合において半順序 (partial order) である」ともいいます.)

つまりトポロジカルソートしたときの末尾となる頂点の個数が分かればいいです.


問題文通りに辺を張ると O(N2)O(N^2) 本になって間に合いません.

なので「\subseteq が非負整数全体の集合上で推移律を見たす」ことを利用して辺の本数を削減します.
具体的には,A<220<2×106A < 2^{20} < 2 \times 10^6 の制約を利用します.

新たにグラフ GG' を考えます.GG' には頂点 0,1,2,,22010, 1, 2, \ldots, 2^{20} - 12202^{20} 個の頂点があります. 各頂点について,「それぞれの頂点を表す非負整数から任意の 1 ビットを下げた頂点へ辺を張る」ことを行います.

d=bit_length(A)d = \mathrm{bit\_length}(A) とします.(この問題では d20d \leq 20)

より形式的には,頂点 ii からは,頂点 i&20~,i&21~,i&22~,,i&2d~i \,\&\, \tilde{2^0},\, i \,\&\, \tilde{2^1},\, i \,\&\, \tilde{2^2},\, \dots,\, i \,\&\, \tilde{2^d} (ただし自分以外) の O(d)O(d) 個の頂点へ辺が張られます.

  • 任意の非負整数 uu に対して u~\tilde{u}uu の bitwise NOT.

このようにすると,\subseteq は推移律を満たすので,「任意の 2 非負整数 u,vu, v について『uvu \subseteq v ならば GG' 上で [uv][u \gets v]-path が存在する』」ということになります.


あとは GG' 上で DP を行えばよいです.(GG' ももちろん DAG になります.)

  • DP[x](xA[i]\mathrm{DP}[x] \coloneqq (x \subsetneq A[i] を満たすような 1iN1 \leq i \leq N なる整数 ii が存在する.[True/False])[\mathrm{True}/\mathrm{False}])
  • 初期状態:DP[x]=False(0xmaxA)\mathrm{DP}[x] = \mathrm{False} \scriptsize \; (0 \leq x \leq \max A)
  • 遷移:DP[y]=G上で[yx]-pathが存在する(DP[x](xA\displaystyle \mathrm{DP}[y] = \bigvee_{G' \text{上で} [y \gets x]\text{-path} が存在する}(\mathrm{DP}[x] \lor (x ∈ A かどうか [True/False]))[\mathrm{True}/\mathrm{False}]))

詳しくは実装例も参照してください.

たとえば,d=3d = 3 のときの GG' は次のようになります:

解説:uni_kakurenbo

実装例

Python