以降、\(x\) が \(2\) 個を \(x+1\) を \(1\) 個に変換する操作を操作 \(x\) と呼びます。また、\(A\) に含まれる \(x\) の個数を \(B_x\) と置きます。\(A\) に含まれる整数の最大値は \(\max A + \log N\) になることに注意してください。

このとき、操作 \(x,y(x < y)\) を両方行う場合、先に操作 \(x\) をするとしてよいです。(操作 \(x\) を行ったことによって操作 \(y\) が行えるようになることはあるが、逆はないため)

よって、次のような動的計画法をすることが出来ます。

• \(\mathrm{dp}[i][j] = \)操作 \(k(k\le i)\) を全て行い、今 \(i+1\) が \(j\) 個ある状態のときに、あり得る \(A\) の状態数

操作 \(i+1\) を \(k\) 回行い、初めからある \(B_{i+1}\) の分も加えることで \(\mathrm{dp}[i][j](j \ge 2k)\) から \(\mathrm{dp}[i+1][k+B_{i+1}]\) に遷移が出来ます。

計算量評価をします。\(i\) は \(A\) に含まれうる整数の最大値で抑えることが出来ます。これは最大ケースの場合の \(\mathrm{O}(\log N + \max A)\) です。\(j\) は \(|A|\) で抑えることが出来ます。これは \(\mathrm{O}(N)\) です。よって遷移を累積和で高速化することによって \(\mathrm{O}(N(\log N + \max A))\) でこの問題を解くことが出来ます。

ですが、このままでは間に合いません。ここで、\(\mathrm{dp}[i]\) の長さに注目します。\(A\) の中の \(i\) 以下の要素 \(j\) に対する \(2^j\) の総和は、操作によって減るか変わりません。よって、「操作中に含まれる \(i\) の個数の最大値」\( \le \frac{\sum_{j=1}^{i} B_j 2^j}{2^i}\) が成り立ちます。

よって、

\(\sum_{i=1}^{\max A + \log N}\)「操作中に含まれうる \(i\) の個数の最大値」 \(\le \sum_{i=1}^{\max A + \log N} \frac{\sum_{j=1}^{i} B_j 2^j}{2^i}\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{\max A + \log N} \sum_{j=1}^{i} B_j\left(\frac{1}{2}\right)^{i-j} \)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{j=1}^{\max A + \log N} \sum_{i=j}^{\max A + \log N} B_j\left(\frac{1}{2}\right)^{i-j} \)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \le\sum_{j=1}^{\max A + \log N} 2B_j\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \le 2N\)

よって \(\mathrm{dp}[i][0]\) のことも考え、\(\mathrm{dp}[i]\) の長さの総和を \(\mathrm{O}(N + \max A)\) と評価出来たため、先ほどの動的計画法を累積和で高速化することによって \(\mathrm{O}(N + \max A)\) でこの問題を解くことが出来ます。