080 - Let's Share Bit（★6）
解説
/ 
/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点: 6 点
問題文
N 個の非負整数 A_1,A_2,\ldots,A_N があります。
0 以上 2^D 未満の整数 x のうち、i=1,2,\ldots,N すべてについて次の条件を満たすようなものはいくつあるか、求めてください。
- A_i と x のビットごとの論理積（ビット単位\operatorname{AND}）が 0 でない。
ビットごとの論理積（ビット単位\operatorname{AND}）について
非負整数 A,B のビットごとの論理積（ビット単位\operatorname{AND}）、A\ \operatorname{AND}\ B は以下のように定義されます。
- A\ \operatorname{AND}\ B を二進表記した際の 2^k\ (k\geq0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
制約
- 1\leq N\leq20
- 0\leq D\leq60
- 0\leq A_i<2^D\ (1\leq i\leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N D A_1 A_2 \cdots A_N
出力
N 個の条件をすべて満たす整数 x の個数を出力してください。
入力例 1
4 3 1 3 4 5
出力例 1
2
0 以上 2^3 未満の整数 x はそれぞれ次の条件を満たします。
- 0 はどの条件も満たさない。
- 1 は 1,2,4 つ目の条件を満たすが、3 つ目の条件を満たさない。
- 2 は 2 つ目の条件を満たすが、1,3,4 つ目の条件を満たさない。
- 3 は 1,2,4 つ目の条件を満たすが、3 つ目の条件を満たさない。
- 4 は 3,4 つ目の条件を満たすが、1,2 つ目の条件を満たさない。
- 5 は全ての条件を満たす。
- 6 は 2,3,4 つ目の条件を満たすが、1 つ目の条件を満たさない。
- 7 は全ての条件を満たす。
よって、答えは 2 です。
入力例 2
5 21 1050624 32772 493952 144 869120
出力例 2
869120
入力例 3
20 60 216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760
出力例 3
977902973481140224
入力や出力すべき値が 32 ビット整数に収まらない場合があります。