P5175 Sequence

Solution: https://blog.csdn.net/kkkksc03/article/details/85008130

Given a sequence $a_n$, where $a_1$ and $a_2$ are known. The sequence $a_n$ satisfies the recurrence $a_n = x \times a_{n-1} + y \times a_{n-2} \ (n \ge 3).$ Compute $\sum_{i=1}^n a_i^2$. Since the answer may be very large, output it modulo $10^9+7$.

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain $5$ integers $n, a_1, a_2, x, y$, with the meanings as described above.

Output $T$ lines, each containing one integer, the answer for each test case.

Sample explanation: For the first sample, the sequence is $1, 1, 2, 3, 5$, so the answer is $1^2 + 1^2 + 2^2 + 3^2 + 5^2 = 40$. For the second sample, the sequence is $3, 4, 18, 62$, so the answer is $3^2 + 4^2 + 18^2 + 62^2 = 4193$. ~~The third sample will not be explained.~~ For the first $20\%$ of the testdata, it is guaranteed that $x = y = 1$. For $100\%$ of the testdata, $T = 30000$, $1 \le n \le 10^{18}$, $1 \le a_1, a_2, x, y \le 10^9$. Translated by ChatGPT 5