bitDPを行う解法を紹介します。

まず、次のような集合列 \(T\) を用意します。(\(2^d\) の位の桁を \(d\) 桁目と表現します。)

\(T_d := (A_iのd桁目に\text{bit}が立っているようなiの集合)\)

そして、 \(dp[d][S]\) を「\(x\) の下から \(d\) 桁を確定したとき、既に \(x \text{ AND } A_i \neq 0\) となっている \(i\) の集合が \(S\) のときの通り数」と定義して、bitDPを行います。

正当性は、ある \(d\) について \(x\) の \(d\) 桁目と \(A_i\) の \(d\) 桁目がともに \(1\) のとき、 \(x\) の他の桁によらず \(x \text{ AND } A_i \neq 0\) となることから従います。

\( dp[d][S] := \left\{ \begin{array}{ll} 1 & \text{if } d = 0 \text{ and } S = \varnothing \\ 0 & \text{otherwise} \end{array} \right. \) と初期化し、 \(d (0 \leq d \leq N-1)\) の昇順に

\( dp[d+1][S] := dp[d+1][S] + dp[d][S] \\ dp[d+1][S \cup T_d] := dp[d+1][S \cup T_d] + dp[d][S] \)

と更新していけば良いです。答えは \(dp[D][\{1, 2, \ldots, N\}]\) となります。

計算量は \(O(2^ND)\) になります。 \(S\) (bit表現とみなしたもの)の降順に処理することで、DP配列をin-placeに更新することもできます。

実装例(C++) (339 ms)

実装例(Python, in-place) (196 ms)