P5175 數列

$$\begin{gathered} a_n^b={\left(x\times a_{n?1}+y\times a_{n?2}\right)}^2 \\ {x}^2\times a_{n?1}^2+y^2\times a_{n?2}^2+2\times x\times y\times a_{n?1}{a}_{n?2} \\ {x}^2\times a_{n?1}^2+y^2\times a_{n?2}^2+2\times x\times y\times a_{n?2}\left(x\times a_{n?2}+y\times a_{n?3}\right) \\ {x}^2\times a_{n?1}^2+y^2\times a_{n?2}^2+2\times x\times y\times \left(x\times a_{n?2}^2+y\times a_{n?2}\times a_{n?3}\right) \end{gathered}$$
$S_{n+1}=S_n+a_{n+1}^2$,

$a_{n+1}^2=x^2\times a_n+y^2\times a_{n?1}+2\times x\times y\times a_n\times a_{n?1}$,

$a_{n+1}{a}_n=x\times a_n^2+y\times a_n\times a_{n?1}$,

$\left[\begin{array}{cccc}{S}_n& a_n^2& a_{n?1}^2& a_n{a}_{n?1}\end{array}\right]$ $\times$ $?\begin{array}{cccc}1& 0& 0& 0\\ x^2& x^2& 1& x\\ y^2& y^2& 0& 0\\ 2\times x\times y& 2\times x\times y& 0& y\end{array}?$

#include <bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;inline int add(int x, int y) {return x + y < mod ? x + y : x + y - mod; }struct Matrix {int a[4][4]; };Matrix operator * (Matrix a, Matrix b) {Matrix ans;for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {ans.a[i][j] = 0;for (int k = 0; k < 4; k++) {ans.a[i][j] = add(ans.a[i][j], 1ll * a.a[i][k] * b.a[k][j] % mod);}}}return ans; }int main() { // freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int T;scanf("%d", &T);while (T--) {long long n;int a1, a2, x, y;scanf("%lld %d %d %d %d", &n, &a1, &a2, &x, &y);if (n == 1) {printf("%d\n", 1ll * a1 * a1 % mod);}else if (n == 2) {printf("%d\n", add(1ll * a1 * a1 % mod, 1ll * a2 * a2 % mod));}else {Matrix ans = {add(1ll * a1 * a1 % mod, 1ll * a2 * a2 % mod), int(1ll * a2 * a2 % mod), int(1ll * a1 * a1 % mod), int(1ll * a1 * a2 % mod),0, 0, 0, 0,0, 0, 0, 0,0, 0, 0, 0,};Matrix a = {1, 0, 0, 0,int(1ll * x * x % mod), int(1ll * x * x % mod), 1, x,int(1ll * y * y % mod), int(1ll * y * y % mod), 0, 0,int(2ll * x * y % mod), int(2ll * x * y % mod), 0, y};n -= 2;while (n) {if (n & 1) {ans = ans * a;}a = a * a;n >>= 1;}printf("%d\n", ans.a[0][0]);}}return 0; }

總結

以上是生活随笔為你收集整理的P5175 数列（矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。