まず、多項式 \(f(x)\) に対し、スコアを最大化する操作方法は次のものです。

正整数 \(k\) を大きい方から見ていって、\(f(x)\) が \((1+x^k)\)で割り切れる限り割っていく。

証明: \(f(x)\) を割り切る \((1 + x^k)\) という多項式のうち、\(k\) が最大のもので、割らない場合に、スコアを最大値する操作方法を考える。そのような操作方法では、\((1 + x^{l_1}),\ldots ,(1 + x^{l_m})\)で割っていくとする。ここで、\(S = \{l_1,\ldots l_m\}\) 、として多重集合を定めると、その部分集合 \(T = \{l_{i_1},\ldots,l_{i_p}\}\)で、\((1 + x^{l_{i_1}}),\ldots, (1 + x^{l_{i_p}})\)で割らないことで、\((1 + x^k)\) で割るようにできるようなものがある。 このとき、 \((1 + x^k)\)は重根を持たないので、\(T\)は重複する元がないように選ぶことができる。仮定より、\(T\) の元は 全て \(k\) 未満なので、\(\sum_{x\in T} 2^x < 2^k\) が成立するので、\((1 + x^{l_1}),\ldots ,(1 + x^{l_m})\)で割っていく操作方法は最適にならない。

この操作方法を愚直に実行すると \(d\) 次の多項式 \(f(x)\) に対し、割り算は \(O(d)\) の時間計算量を必要とし、最大で\(d\)回割り算を行うので \(O(d^2)\) の時間計算量で、\(f(x)\) のスコアを計算できます。 制約より、全体の計算量は \(O(QN^2)\) となり、制限時間内に計算が終わらない場合があります。

そこで、この問題を \(O(QN + N^2logN)\) の時間計算量で解く方法を紹介します。 解法の全体像としては、与えられた全ての多項式に対して、\((1 + x^k)\) \((1\leq k \leq N)\) で何回割れるかわかっていれば、\(O(QN)\) の時間計算量でこの問題を解くことができます。そのために、各多項式が、\((1 + x^k)\) で割れる回数を判定する方法を紹介します。 以降、多項式として、0でないもののみを考えます。 (0 の場合は、クエリの答えは明らかに 0 です)

\((1 + x^k)\) で割れるか判定する方法

多項式 \(f(x)\) が \((1 + x^k)\) で割り切れることは、以下の \(k\) 個の条件を全て満たすことと同値です。

・ \([x^0]f - [x^k]f + [x^{2k}]f - \ldots = 0\)

・ \([x^1]f - [x^{k + 1}]f + [x^{2k + 1}]f - \ldots = 0\)

\(\vdots\)

・ \([x^{k - 1}]f - [x^{2k - 1}]f + [x^{3k - 1}]f - \ldots = 0\)

ここで、\([x^i]f\) は \(f(x)\) の \(i\) 次の係数を表します。 このように、 \((1+x^k)\) で割り切れることは、\(k\) 個おきの交代和の条件でかけます。与えられる多項式は係数が区間の形をしているので、交代和の累積和をとって、ハッシュ関数を用いることで、\(f(x) = \sum_{j=0}^{r_i - l_i}A_{j + l_i}x^{j}\)が \((1 + x^k)\) の倍数かは、\(O(1)\) で判定できます。

\((1 + x^k)\) で割れる回数を計算する方法

まず\(f(x)\) が \((1 + x^k)\) で \(m\) 回割れる \(\Leftrightarrow\) \(0 \leq j \leq m - 1\) なる全ての \(j\) について、\(\frac{d^jf(x)}{dx^j}\) が \((1 + x^k)\) の倍数になる という性質が帰納法によって証明できます。

この性質より、微分したものに対して、\((1 + x^k)\) の倍数か判定していって、\(m\) 回微分したときに、初めて \((1 + x^k)\) の倍数でなくなったら、\((1 + x^k)\) で \(m\) 回割れると分かります。 全体の次数が、\(N\) 以下なので、\((1 + x^k)\) で割れる回数は \(N/k\) 回以下です。各整数 \(k\) について、\(N/k\) 回微分まで見ればよいです。

クエリに答える方法

冒頭で紹介したように、大きい次数から割っていけばよいです。 ただし、注意点として、\((1 + x^k)\) で割れる回数は、\(k\) の奇数の約数 \(d\) に対し、\((1 + x^{\frac{k}{d}})\) で割れる回数が減ります。これは、ざっくり説明すると\((1 + x^k)\) が、\((1 + x^{\frac{k}{d}})\) の倍数となることに起因します。 より詳細には、\((1 + x^k)\) で割ると、\(l\neq k\)なる \(l\) に対し、 \((1 + x^l)\) で割れる回数がどのように変化するか、考察する必要があります。実は、\(\gcd((1 + x^k),(1 + x^l))\) は、\(k\) と \(l\) の \(2\) で割れる回数が等しいなら、\((1 + x^{gcd(l,k)})\), そうでないなら \(1\) になります。これを踏まえると、\((1 + x^k)\) で割れる回数は、\(k\) の奇数の約数 \(d\) に対して、\((1 + x^\frac{k}{d})\) で割れる回数の最小値に等しく、 \((1 + x^k)\) で割るたびに、\((1 + x^{\frac{k}{d}})\)で割れる回数を割った回数だけ減らす必要があります。 割った後の数でも、\((1 + x^k)\) で割れる回数たちを正しく保持できれば、\((1 + x^k)\) で大きい方から割っていく操作を高速にシミュレーションできます。

全体の計算量ですが、まず整数\(k\) \((1\leq k \leq N - 1)\)に対して、\(j\) \((1\leq j \leq \frac{N}{k})\) 回微分したものについて、\(k\) 個おきの交代和の累積和をとるパートで、\(O(N^2logN)\)かかります。微分して、交代和の累積和を取る過程で、各クエリで与えられた多項式が \((1 + x^k)\) で割り切れるか判定する必要がありますが、実は各多項式について、見るべき多項式は \(N\) 個以下なので、各判定が \(O(1)\) なので、このパートもクエリに答えるパートも \(O(QN)\) となります。 以上をまとめて、時間計算量 \(O(QN + N^2logN)\) でこの問題を解くことができます。

原案 : Alt3

解答 改題 : Alt3, noimi