\(\sum\limits_{k=1}^N \sum\limits_{x=1}^M b_k k^x\) の方は等比数列の公式などを使えば求めることができます。 ただし、\(k=1\) の場合は場合分けが必要なので注意してください。以下、\(\sum\limits_{k=1}^N \sum\limits_{x=1}^M a_k x^k\) について考えます。

小課題１

\(S_m=\sum\limits_{k=1}^N \sum\limits_{x=1}^m a_k x^k\) とおきます。

\(\left( \begin{matrix} 1 \\ m+1 \\ (m+1)^2\\ (m+1)^3\\ \vdots \\ (m+1)^N\\ S_m \end{matrix} \right) =\left( \begin{matrix} 1 & 0 & 0 & 0 & \dots & 0 & 0 \\ 1 & 1 & 0 & 0 & \dots & 0 & 0 \\ 1 & 2 & 1 & 0 & \dots & 0 & 0 \\ 1 & 3 & 3 & 1 & \dots & 0 & 0 \\ \vdots \\ _{N}C_0 & _{N}C_1 & _{N}C_2 & _{N}C_3 & \dots & _{N}C_N & 0 \\ 0 & a_1 & a_2 & a_3 & \dots & a_N & 1 \\ \end{matrix} \right) \left( \begin{matrix} 1 \\ m \\ m^2\\ m^3\\ \vdots \\ m^N\\ S_{m-1} \end{matrix} \right)\)

を利用して行列累乗を用いると、\(O(N^3\log M)\) で解くことができます。

小課題２

\(f(M) = \sum\limits_{k=1}^N \sum\limits_{x=1}^M a_k x^k\) とおくと、 \(f\) は \(N+1\) 次の多項式になります。\(f(0),f(1),\dots , f(N+1)\) がわかれば、多項式補間により \(f(M)\) を求めることができます。計算量は \(O(N^2)\) です。

満点

\(1^k+2^k+\dots + M^k\) を \(k=1,2,\dots , N\) について求めることを考えます。

\(e^x=1+1x+\frac{1^2}{2!}x^2+\frac{1^3}{3!}x^3+\dots\)

\(e^{2x}=1+2x+\frac{2^2}{2!}x^2+\frac{2^3}{3!}x^3+\dots\)

\(\vdots\)

\(e^{Mx}=1+Mx+\frac{M^2}{2!}x^2+\frac{M^3}{3!}x^3+\dots\)

これらを縦に足すと、\(x^k\) の係数に \(k!\) をかけたものが\(1^k+2^k+\dots + M^k\) になっています。

\(e^x+e^{2x}+\dots +e^{Mx}=\frac{e^x-e^{(M+1)x}}{1-e^x}\)

の \(x^k\) の係数が \(k=1,2,\dots,N\) について求まればよく、これはfpsの除算によって \(O(NlogN)\) でできます。

おまけ

当初は \(N\leq 200000\) の解法が多点評価を用いた \(O(N {\log N}^2)\) しかわかっていなくて \(N \leq 5000\) を満点にする予定でしたが、testerのmaspyさんに \(O(N \log N)\) で解けることをご指摘いただき、 \(N\leq 200000\) で出題することにしました。ありがとうございます。