東京海上日動プロコン2020 E問題 - "O(rand)" 解説
ARC級のE問題、本番中のACは 88人 / 223人提出 で、Diff 2726 と、かなり難しい判定の出ている問題です。
実際、考察や実装自体は難しかったですが、要求される知識自体は「包除原理」以外には高度なものは無く、緑コーダーの知識でも十分解けるものでした。
こういった問題がコンテスト中に解けると一気にレートが上がると考えているので、どんどん攻略していきたいですし、折角攻略したので共有したいと思い、解説します。
概要
N個の相異なる非負整数 A1, A2, ..., AN があって、そこから 1～K個の数を選ぶ。
その選び方のうち、次の2つの条件を満たすような選び方の組合せは何通りあるか。
(1) 選んだ数の全てについてビットごとにANDをとっていき、答えがSになる
(2) 選んだ数の全てについてビットごとにORをとっていき、答えがTになる
制約：1<=N<=50, 0<=Ai, S, T < 2^18, Ai≠Aj など
大雑把な方針
そのまま考えると非常に難しいので、3パートに分けます。
パート1：コーナーケースの処理
(1) S[d]=1, T[d]=0 となっているような桁があれば、条件を満たすのは無理なので答えは 0
(2) S=T のときを処理（S=T=AiとなるようなAiがあれば答えは1, なければ答えは0）
※(2)の説明
S=Tの時、全ての桁でS[d]=T[d]=0 or S[d]=T[d]=1 となっている。
すると、S[d]=T[d]=0となっている桁は0しか選べないし、S[d]=T[d]=1となっている桁は1しか選べない。
ということは、例えば S[d]=T[d]=00101010 なら Ai も 00101010 しか選べないが、制約から各Aiは相異なるので、そのようなAiは「1つしかない（＝選び方1通り） or 1つもない（選び方0通り）」のどちらかであるため。
パート2：簡略化パート
2つの「除外」を行って、問題を簡略化します。
※ [d] はd桁目のビット を表すことにします。
(1a) S[d]=T[d]=0 となっているような桁では、Ai[d]=0 となっているような Ai しか選べないので、各 Ai のうち、Ai[d]=1 となっているものを除外してしまう
(1b) S[d]=T[d]=1 となっているような桁では、Ai[d]=1 となっているような Ai しか選べないので、各 Ai のうち、Ai[d]=0 となっているものを除外してしまう
(2) (1)の結果、S[d]=T[d] であるような桁は、「残っているどのAiを選んでもいい」状態になっています。つまり、「どうでもいい桁」になりました。ということで、桁を削除してしまいます。
※桁の削除の仕方
ビットの計算に慣れていないと、ここが若干面倒だと思います（私は面倒でした）。
説明するのは大変なので、提出コードを参考にしてください。
ざっくり言えば、削除したい桁より上を割り算で取り出し、それらの桁を1つ下げ、削除したい桁より下を余りの計算で取り出し、それらの桁をそのままくっつけました。
簡略化された問題のまとめ
一旦、簡略化された問題を整理しておきます。
・全ての桁について、(S[d], T[d]) = (0, 1) になった
・つまり 残っている各Aiについて、ANDをとると0000…、ORをとると1111… となるような組合せの数を求めたい
この2行目は、以下のように言い換えられます。
・ANDをとると0000... ：「0を1つ以上選ぶ」
・ORをとると 1111...： 「1を1つ以上選ぶ」
つまり
・どの桁を見ても、「0も1もそれぞれ1つ以上」選ばれているような選び方の数を求めたい
このように問題を整理できました。
あとは、本題パートで解いていきたいと思います。
※余事象：真正面から求めるのがつらい時、「場合の数全体 - そうじゃない場合の数」で求める。例：例えば0を1つ以上選ぶ組合せなら、「全ての選び方 - 0を1つも選ばない選び方」など
（注）S[d], T[d] = (0, 1)の桁が一つもないパターンはあるか？
条件に当てはまる桁が一つも無いパターンがあると、コーナーケースになるんじゃないか？
と、不安に思う方もいると思いますが、そういったコーナーケースは残っていません。
何故なら、(1, 0) パターンがある場合はパート1で処理されており、「全てが(0, 0) or (1, 1)」というパターンについても、そのパターンは「S=Tの場合」とイコールなので、やはりパート1で処理されているからです。
パート3：本題パート
（再掲）
・どの桁を見ても、「0も1もそれぞれ1つ以上」選ばれているような選び方の数を求めたい
「1つ以上選ぶ」という言葉が出てきて、にわかに余事象っぽくなってきました。
ただし、単なる余事象では計算できない複雑な組合せのため、そのような場合に使う「包除原理」を活用します。
なぜ普通の余事象で解けないか
一応、まずは普通の余事象で考えてみます。
（強い人からすると、いやいやそりゃ無理でしょという感じだと思いますが、慣れていないと違いが分かりにくいと思うので）
ある桁について、「0も1もそれぞれ1つ以上選ぶ」の余事象ですから、「0だけ選ぶ」か「1だけ選ぶ」のどちらかです。
これらの場合の数は、その桁の「0の数」と「1の数」が分かれば解けそうです。
しかし、ある1つの桁についての選び方の場合の数が分かっても、その選び方は具体的に分からないので、次の桁を考える時に「この選び方は前の桁の選び方と矛盾するのか？しないのか？」というところが分かりません。
こんな風に、余事象の考え方だけではどうしようもなくなってしまいます。
包除原理での考え方（立式）
（包除原理についての詳しい説明は ここ や ここ などを参考にしてください。）
包除原理は、「沢山の条件の『当てはまる・当てはまらない』を組合せて、最終的に目的の場合の数を求める」みたいなことができます。
その際、「条件の組み方」が大事になりますが、今回は、以下の2条件（A, B）を組み合わせることにします。
（条件A）Ai[d]が 全部0 もしくは 全部1 となるような選び方（0, 1のどちらか一方だけから全部取る）
（条件B）Ai[d]は 何をどう選んでもいい
※どうやって条件A, Bを持ってきたのか？
元々ある条件は、「(a)全部0 (b)全部1 (c)0と1混合」の3つであり、今回求めたいのは「全ての桁において (c) となる選び方」です。
ということは、包除原理も余事象の延長なので、(c) の余事象 つまり「0と1が混ざっていない＝全部0もしくは全部1」を条件にするというわけです。
この2条件を各桁に組み合わせて（包除原理に基づいて式を立てて）、問題を解きます。
＜出来上がる式＞
（例：残り桁数 4桁, 残っているAiの数 5）
求める答え = BBBB -BBBA -BBAB -BABB -ABBB +BBAA +BABA +BAAB +ABBA +ABAB +AABB -BAAA -ABAA -AABA -AAAB +AAAA
（包除原理の式は、満たす条件が奇数の場合「-」になり、偶数の場合「+」となる）
※BBAB といった書き方は、各桁が条件A（全部0か全部1）と条件B（何でもいい）のどちらに当たるか（及びその時の場合の数）を表します。
各項の計算法
包除原理によって式を立てることができましたが、各項の計算もなかなか難しいです。
例えば、ABAAの具体的な数（4, 2, 1桁目は全部0or全部1で、3桁目はどちらでもいいような選び方）というのは、どのように求めればいいでしょうか？
これは、下図のように「グループ分け」を考えることで求められます。
上図は、ABAA となるような選び方を示しています。
まず、Bの桁は何でもいいので、無視します（灰色で塗りつぶしました）。
次にAの桁ですが、これらは「各桁毎に、全部0か全部1」ですから、「取り出した組合せが、縦に見て全部0or全部1」になっていないといけません。
つまり、図中で色分けした1つのグループ（青、橙、緑、紫）のうち、1つのグループのみから選ぶ（グループをまたがって選ばない）必要があります。
ということは、ABAA の具体的計算は、以下のようになります。
ABAA = [青グループから1～K個選ぶ選び方] + [橙グループから1～K個選ぶ選び方] + [緑グループから1～K個選ぶ選び方] + [紫グループから1～K個選ぶ選び方]
もちろん BABB や BBBA などについても同じなので、これが計算できれば先程の式の答えは求められる＝問題に答えられる ということになります。
ここからの計算も私（緑コーダー）にとって簡単ではなかったですが、
ここから先は、茶上位～緑レベルの人がウンウン唸って頑張れば十分に解ける難易度だと思いますので、説明しないでおきます。
（提出コードにコメントを沢山入れましたので、必要になれば参考にしてください。）
ヒントとしては、「連想配列（map）のバケツ」「マスクビット」などがあります。
その他の注意点
・nCkの計算時、オーバーフローさせないように注意。私はここで割と詰まりました。
