思考の過程が想定解と違ったので．（追記）答えは合うのですがかなり怪しいところがあるので，正当性の証明（または反例）を募集しています．
解法
長さ \(2^N\) の配列同士の (bitwise) OR convolution: $$ (f \ast g)[i] = \sum_{(j | j') = i} f[j] g[j']$$ を表す演算を \(\ast \) と書くことにする．また，長さ \(2^N\) の配列 \(e[i]\) を， $$ e[i] = \cases{ 1 & $i = 0$ \\ 0 & $i = 1, \ldots, 2^N - 1$ } $$ と定義すると，この \(e\) は演算 \(\ast\) に関して単位元となる（任意の \(f\) について \( e \ast f = f \ast e = f\) が成立）．
また，本問における状態遷移確率を表す長さ \(2^N\) の配列 \(g[i]\) を， $$ g[i] = \frac{A[i]}{\sum_{j=0}^{2^N - 1} A[j]}$$ とおく．ある時点において，それまでに手に入った整数の論理和の値が \(i\) であるような確率が \(f[i]\) であるような配列 \(f\) があったとして，新たにもう一つの整数を手にいれた場合の論理和の値の確率分布は \(f \ast g\) で書ける．先ほど定義した \(e\) は本問の状況における確率分布の初期値となる．
本問で最終的に求めたい値は \(i\) の全ビットが on になるまでの時間の期待値であるが，これは「\(t\) 回ガチャを回し，未だに on になっていないビットが存在する確率」の \(t = 0, 1, \ldots\) に関する総和と言い換えられる．したがって，この値は $$ \sum_{i=0}^{2^N - 2} \left( e[i] + (e \ast g)[i] + (e \ast g \ast g)[i] + (e \ast g \ast g \ast g)[i] + \ldots \right)$$ と書き表せる．とりあえず \(e + (e \ast g) + (e \ast g \ast g) + \ldots \) が収束するものと仮定し（パチンコ）*1，これを \(h\) とおくと，この \(h\) が求められれば本問題は解けたことになる．
\(h\) に関して，$$e + (h \ast g) = h$$ すなわち $$h \ast (e - g) = e$$ が成り立つ．演算 \(\ast\) が「各配列のゼータ変換・2配列の対応する要素同士の要素積・配列のメビウス変換（ゼータ変換の逆変換）」と書けることを考えると，（通常の OR convolution の順序を逆に辿ることで）既知の \(e\) および \(e - g\) から \(h\) が求められる*2．よって本問は解けた．
