题解

思路

直接递推

当所有询问的 $n$ 之和不超过 $10^6$ 时，逐项计算数列并累加平方即可，复杂度为 $O(\sum n)$。

$x=y=1$ 的恒等式

令 $a_0=a_2-a_1$，则递推对 $k\ge1$ 都满足 $a_{k+1}=a_k+a_{k-1}$。于是

$$a_k^2=a_ka_{k+1}-a_{k-1}a_k.$$

求和后得到

$$\sum_{k=1}^{n}a_k^2=a_na_{n+1}-a_0a_1.$$

再利用 Fibonacci 快速倍增求 $a_n,a_{n+1}$，每组询问只需 $O(\log n)$。

做法

一般系数的四维状态

记 $S_k=\sum_{i=1}^k a_i^2$。为了展开平方，还需同时维护相邻两项的平方与乘积。取状态

$$v_k=\begin{bmatrix}S_k\\a_k^2\\a_{k-1}^2\\a_ka_{k-1}\end{bmatrix}.$$

由 $a_{k+1}=xa_k+ya_{k-1}$，有

$$a_{k+1}^2=x^2a_k^2+y^2a_{k-1}^2+2xy\,a_ka_{k-1},$$

以及

$$a_{k+1}a_k=xa_k^2+y\,a_ka_{k-1}.$$

因此

$$v_{k+1}= \begin{bmatrix} 1&x^2&y^2&2xy\\ 0&x^2&y^2&2xy\\ 0&1&0&0\\ 0&x&0&y \end{bmatrix}v_k.$$

初始状态为

$$v_2=\begin{bmatrix}a_1^2+a_2^2\\a_2^2\\a_1^2\\a_1a_2\end{bmatrix}.$$

对转移矩阵计算 $n-2$ 次幂即可。实现中一次矩阵乘法的每个单元只累加四个小于模数平方的乘积；其和不会超过无符号 64 位整数范围，因此可在每个单元累加完后只取模一次，以适应最多 $30000$ 组询问。

独立复核递推

设 $b_k=a_k^2$，特征根关系可推出

$$b_k=(x^2+y)b_{k-1}+y(x^2+y)b_{k-2}-y^3b_{k-3}.$$

再乘上前缀和对应的因子 $(t-1)$，可得到 $S_k$ 的四阶线性递推。正式输出由这一递推配合多项式快速幂独立复算，从而不依赖标准程序的矩阵实现。

正确性证明

引理 1

当 $x=y=1$ 时，恒等式 $\sum_{k=1}^{n}a_k^2=a_na_{n+1}-a_0a_1$ 成立。

证明。 由递推式 $a_{k+1}-a_{k-1}=a_k$，两边乘以 $a_k$ 得 $a_k^2=a_ka_{k+1}-a_{k-1}a_k$。从 $1$ 到 $n$ 求和后中间项全部抵消。∎

引理 2

一般系数下，上述矩阵把 $v_k$ 正确转移为 $v_{k+1}$。

证明。 第二行是递推式平方后的展开，第三行把旧的 $a_k^2$ 下移，第四行由递推式乘以 $a_k$ 得到；第一行在 $S_k$ 上加上第二行的新平方。四个分量均与定义一致。∎

定理

算法对每组询问输出 $\sum_{i=1}^{n}a_i^2\bmod(10^9+7)$。

证明。 $n=1,2$ 直接计算。对 $n\ge3$，初始向量确为 $v_2$；由引理 2，乘以转移矩阵的 $n-2$ 次幂后得到 $v_n$，其第一分量按定义就是所求平方和。所有运算在模意义下进行，故输出正确。∎

复杂度

满分算法每组询问时间复杂度 $O(4^3\log n)=O(\log n)$，额外空间复杂度 $O(1)$；总时间复杂度为 $O(T\log n)$。