矩阵 $\LaTeX$ ：

\begin{bmatrix}
1 & 1 & 4 \\\\
5 & 1 & 4
\end{bmatrix}

P1962 斐波那契数列

题意

求斐波那契数列第 $n$ 项，对 $10^9+7$ 取模。 $1\le n\le2^{63}$ 。

点击查看题解

题解

构造矩阵 $A=\begin{bmatrix}1 & 1\\\\1 & 0\end{bmatrix}$ ， $B=\begin{bmatrix}f_2 & f_1\end{bmatrix}$ 。则有：

\begin{aligned} BA&=\begin{bmatrix}f_2+f_1 & f_2\end{bmatrix}=\begin{bmatrix}f_3 & f_2\end{bmatrix} \\\\ BA^2&=\begin{bmatrix}f_3+f_2 & f_3\end{bmatrix}=\begin{bmatrix}f_4 & f_3\end{bmatrix} \\\\ BA^{n-2}&=\begin{bmatrix}f_{n-1}+f_{n-2} & f_{n-1}\end{bmatrix}=\begin{bmatrix}f_n & f_{n-1}\end{bmatrix} \end{aligned}

因为结合律，可得：

BA^k=B(A^k)

矩阵快速幂求之。

可见，矩阵加速递推的关键就在矩阵的构造。之后的题解，递推矩阵都会以注释的形式出现在代码中。

代码

下面的代码中，结构体 Matrix 的定义参加文章“Matrix”。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=200+10,mod=1000000007;
	ll n,init[]={1,1,1,0},ans;
	Matrix A(2,init);
	void main()
	{
		scanf("%lld",&n);
		if(n<=2){printf("1");return;}
		A^=n-2; ans=A.M[1][1]+A.M[2][1];
		printf("%lld\n",ans%mod);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
|1,1|
|1,0| x |f1,f2| = |f1+f2,f2|
*/

P1939 【模板】矩阵加速（数列）

题意

已知一个数列 $a$ ，它满足：

a_x= \begin{cases} 1 & x \in\{1,2,3\}\\\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases}

求 $a$ 数列的第 $n$ 项对 $10^9+7$ 取余的值**。多组询问**。

对于 $100\%$ 的数据 $1 \leq T \leq 100$ ， $1 \leq n \leq 2 \times 10^9$ 。

点击查看题解

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=200+10,mod=1000000007;
	ll n,init[]={0,0,1,1,0,0,0,1,1},ans;
	void main()
	{
		ll T;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			if(n<=3){printf("1\n");continue;}
			Matrix A(3,init);
			A^=n-3; ans=A.M[1][3]+A.M[2][3]+A.M[3][3];
			printf("%lld\n",ans%mod);
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
|f1,f2,f3| 

|0,0,1| 
|1,0,0| 
|0,1,1| 

|f2,f3,f1+f3|

|f3,f1+f3(f4),f1+f2+f3(f2+f4)|

1,1,1,2,3,4,6,9,13,19
*/

P4838 P哥破解密码

题意

定义一个串合法，当且仅当串只由字符 A 和 B 构成，且没有连续的 $3$ 个 A。求长度为 $N$ 的合法字符串数量对 $19260817$ 取模的结果**。多组询问**。

$N\leq 10^9$ ， $T\leq 10$ 。

点击查看题解

题解

长度为 $N$ 的合法字符串，有三种情况：

第 $N$ 位是 B。此时方案数为长度为 $N-1$ 的合法字符串数（因为后面只会追加一个 B，只要前面合法，则追加后也一定合法）。
第 $N$ $N$ 位是 A。
- 第 $N-1$ 位是 B。此时方案数为长度为 $N-2$ 的合法字符串数（即便 $N-2$ 位是 A，第 $N-1$ 位也把它分开了）。
- 第 $N-1$ 位是 A。此时方案数为长度为 $N-3$ 的合法字符串数（即长度为 $N-2$ 的合法字符串数减去长度为 $N-2$ 的末尾是 A 的合法字符串数）。

分类完成，递推式是：

a_x= \begin{cases} 2 & x=1\\\\ 4 & x=2\\\\ 7 & x=3\\\\ a_{x-1}+a_{x-2}+a_{x-3} & x \geq 4 \end{cases}

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=200+10,mod=19260817;
	ll n,init[]={0,0,1,1,0,1,0,1,1};
	void main()
	{
		ll T;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld",&n);
			Matrix A(3,init);
			A^=n+1; 
			printf("%lld\n",A.M[3][3]);
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
|a,b,c|

|0,0,1|
|1,0,1|
|0,1,1|

|b,c,a+b+c|
*/

1643：【例 3】Fibonacci 前 n 项和

题意

求斐波那契数列前 $n$ 项和 $\bmod m$ 。

$1≤n≤2\times10^9$ ， $1≤m≤10^9+10$ 。

点击查看题解

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=200+10;
	ll mod;
	ll n,m,init[]={0,1,1,1,1,1,0,0,1},ans;
	void main()
	{
		scanf("%lld%lld",&n,&mod);
		Matrix A(3,init);
		if(n==1) printf("1\n");
		else if(n==2) printf("2\n");
		else
		{
			A^=n-2;
			ans=A.M[1][3]+A.M[2][3]+A.M[3][3]*2;
			printf("%lld\n",ans%mod);
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
a1,a2,s
1,1,2

0,1,1,
1,1,1,
0,0,1

a2,a1+a2,s+a1+a2
1,2,4
*/

P5175 数列

题意

一个数列 $a_n$ ，已知 $a_1$ 及 $a_2$ 两项。

数列 $a_n$ 满足递推式：

a_n=x \times a_{n-1}+ y \times a_{n-2}(n\ge3)

求：

\sum_{i=1}^na_i^2

由于答案可能过大，对 $10^9+7$ 取模。

点击查看题解

题解

本题递推矩阵构造具有技巧性，详情看代码。

思想是**：我需要知道哪些信息来进行递推，以及如何维护这些信息**。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=5,mod=1000000007;
	ll n,a1,a2,x,y,ans,a,b,c,d; 
	void main()
	{
		ll T;
		scanf("%lld",&T);
		while(T--)
		{
			scanf("%lld%lld%lld%lld%lld",&n,&a1,&a2,&x,&y);
			a1%=mod; a2%=mod; x%=mod; y%=mod;
			ll init[]={0,(2*x%mod*x%mod*y%mod+y*y%mod)%mod,x,0,
			           1,x*x%mod,0,1,
					   0,2*x%mod*y%mod*y%mod,y,0,
					   0,0,0,1};
			Matrix A(4,init);
			if(n==1) printf("%lld\n",a1*a1%mod);
			else if(n==2) printf("%lld\n",(a1*a1%mod+a2*a2%mod)%mod);
			else
			{
				a=a2*a2%mod;
				b=(x*a2%mod+y*a1%mod)%mod*((x*a2%mod+y*a1%mod)%mod)%mod;
				c=a1*a2%mod;
				d=(a1*a1%mod+a2*a2%mod)%mod;
				A^=n-2;
				ans=a*A.M[1][4]%mod+b*A.M[2][4]%mod+c*A.M[3][4]%mod+d*A.M[4][4]%mod;
				printf("%lld\n",ans%mod);
			}
			
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
a_n = xa_{n-1} + ya_{n-2}

a_{n-1}a_{n-2} = (xa_{n-2} + ya_{n-3})a_{n-2}
               = xa_{n-2}^2 + ya_{n-2}a_{n-3}

a_n^2 = (xa_{n-1} + ya_{n-2})^2
      = x^2 a_{n-1}^2 + 2xya_{n-1}a_{n-2} + y^2 a_{n-2}^2
	  = x^2 a_{n-1}^2 + 2xy(xa_{n-2}^2 + ya_{n-2}a_{n-3}) + y^2 a_{n-2}^2
	  = x^2 a_{n-1}^2 + 2x^2 ya_{n-2}^2 + 2xy^2 a_{n-2}a_{n-3} + y^2 a_{n-2}^2
	  = x^2 a_{n-1}^2 + a_{n-2}^2(2x^2 y + y^2) + 2x y^2 a_{n-2}a_{n-3}
               
a_{n-2}^2 a_{n-1}^2 a_{n-2}a_{n-3} s_{n-2}
(a2)^2 (xa2+ya1)^2 a1a2 a1^2+a2^2

0,2x^2 y + y^2,x,0
1,x^2         ,0,1
0,2x y^2      ,y,0
0,0           ,0,1

a_{n-1}^2 a_n^2 a_{n-1}a_{n-2} s_{n-1}
*/