はじめに
「Square」writerのKowerKointです。
通常の全列挙で間に合わないので半分全列挙で高速化すると「Square」が突破でき、通常のbitDPで間に合わないので使うビットを工夫して減らすと「Re:Square」も含めて突破できるという問題でした。
この問題は当初半分全列挙のみを想定したのですが、testerのWA_TLEさんがより高速な解法を発見したため、それに対応した問題が「Re:Square」として採用されました。
解説
半分全列挙による解法(「Square」のみAC)
半分全列挙をします。
つまり、数列$A$を半分ずつに分けて、それぞれの中で作れる整数を列挙します。
$A_1,A_2,\dots A_{N/2}$から作れる整数の多重集合を$S$、$A_{N/2+1},A_{N/2+2},\dots A_{N}$から作れる整数の多重集合を$T$とします。
$S$の要素$s$のそれぞれについて、$s$と掛け合わせて平方数を作る$T$の要素の総和を取りたいです。
したがって、$s$が与えられたときにそれと掛け合わせて平方数をなすものを$T$の中でグループ化しておき、それぞれの$s\in S$について対応するグループに含まれる数の総和を$s$とかけ合わせればよいことがわかります。
平方数を作る$2$つ数の組の性質を考えます。
整数$x$を素因数分解したとき、すべての素因数の指数は偶数であることと$x$が平方数であることは同値です。
これを利用すると、$s$と$t$について$st$が平方数となる必要十分条件は$s$の素因数のうち指数が奇数のものの集合と$t$の素因数のうち指数が奇数のものの集合が一致することであるとわかります。
以上から、$S$と$T$を、「素因数分解したとき指数が奇数になる素因数の集合」でグループ分けしてその総和を予め計算しておけばうまくマージできます。
工夫したbitDPによる解法(「Square」と「Re:Square」をAC)
半分全列挙と同じように、素因数の指数の偶奇に着目します。
各素因数の指数の偶奇をビット列として扱い、dp[i][j]を「$A$のi番目までを使って素因数の指数の偶奇がjのようになるものの総和」とすればビット列の長さを$M$とした$O(N2^M)$時間でのbitDPでこの問題が解けます。
このままでは「Square」の制約では$46$種類、「Re:Square」の制約では$62$種類の素因数が登場し得るため、bitDPでは間に合いませんん。
しかし、$Y$以下の正の整数を素因数分解したとき、$\lceil\sqrt{Y}\rceil$以上の素因数はたかだか1種類しか存在しないことを考えると、$\lceil\sqrt{\max A}\rceil$以上の素因数ごとにグループ化してそれらを連続して処理することにすれば同時に必要な素因数は$\pi(\sqrt{\max A})$($\pi(x)$は$x$以下の素数の個数)程度ですむのです。
以上から、$O(N2^{\pi(\sqrt{\max A})})$時間のbitDPでこの問題が解けました。
ちなみに、おまけですが$A_i<=2000$の制約でもこの問題は解ける(testerのygussanyさんに教えていただきました)ので、余裕があれば考えてみてください。