算法1

我会暴力！

直接写了一个$O(nq)$的暴力。

期望得分5分。

算法2

我会拉板子！

直接拉了一个$O(Q \log^2 n)$的多点求值。

期望得分20分。

算法3

我会拉很牛逼的板子！

期望得分35分。

算法4

我会看性质！

不难发现求的是$q_0*qx^k$的点值。

不难构造函数$g(x)$满足$f(x)=g(x/q_0)$

问题转化为求$V(j)=\sum a_i qx^{ij}$

根据$\binom{i+j}{2}=\binom{i}{2}+\binom{j}{2}+ij$,转写上面的式子。

$V(j) qx^{\binom{j}{2}}=\sum a_i qx^{-\binom{i}{2}} qx^{\binom{i+j}{2}}$

不难发现本质是两个序列做的一次减法卷积。

时间复杂度$O(Q \log Q)$

结合算法3期望得分60分。

算法5

我会推性质！

根据已知条件多点求值暂时没有$O(n\log^2 n)$的算法。

因此随机性质一定有用!。

假设我们已知$n$次多项式$f(x)$,则我们可以:

在$O(n)$的时间复杂度内找到一个$n$次多项式$g(x)$满足$g(x)=f(x*k)$。

在$O(n \log n)$的时间复杂度内找到一个$n$次多项式$h(x)$满足$h(x)=h(x+k)$。

再看看询问的东西，不难发现第i次询问的是$q_0 qx^i+\sum \limits_{j=0}^{j \le i-1} qy qx^j$

乘上$qx-1$得到$q_0 qx^i(qx-1)+qy qx^i-qy$

加上$qy$得到$(q_0(qx-1)+qy)qx^i$

欸变成算法4了！

$q_0(qx-1)+qy$为0时询问值总为0不会产生影响。

同时输入范围保证$qx \geq 2$所以上文所有变换均合法。

由于每一次变换复杂度均为$O(n \log n)$

时间复杂度$O(Q \log Q+n \log n)$

期望得分100分。