矩阵快速幂解线性递推式：
a n = a n − 1 + a n − 3 a_{n}=a_{n-1}+a_{n-3}a n =a n −1 +a n −3
Solution：
一般构造矩阵的时候都构造一个连续的矩阵，且这个矩阵元素下标都+ 1 +1 +1后两个矩阵恰好覆盖了递推式所涉及的所有项，设递推式跨越的下标长度为l e n len l e n，这个长度一般是l e n − 1 len-1 l e n −1，譬如当前构造矩阵
[ a n , a n − 1 , a n − 2 ] [a_{n},a_{n-1},a_{n-2}][a n ,a n −1 ,a n −2 ]
我们需要构造出一个矩阵，使得这个上式矩阵乘构造矩阵后得到
[ a n + 1 , a n , a n − 1 ] [a_{n+1},a_{n},a_{n-1}][a n +1 ,a n ,a n −1 ]
矩阵乘法：
对于两个矩阵a , b a,b a ,b相乘，结果矩阵的i i i行j j j列为
∑ k = 1 n a i , k b k , j \sum_{k=1}^{n}a_{i,k}b_{k,j}k =1 ∑n a i ,k b k ,j
即a a a的i i i行与b b b的j j j列的所有元素对应相乘相加
单位矩阵：
是主对角线元素为1 1 1，其余元素为0 0 0的矩阵，即满足下式的矩阵
a i , j = { 0 i ≠ j 1 i = j a_{i,j}=\begin{cases} 0 & i\neq j\ 1 & i=j \end{cases}a i ,j ={0 1 i =j i =j
根据矩阵乘法的规则构造矩阵为
[ 1 1 0 0 0 1 1 0 0 ] \left[ \begin{matrix} 1 & 1 & 0\ 0 & 0 & 1\ 1 & 0 & 0 \end{matrix} \right]⎣⎡1 0 1 1 0 0 0 1 0 ⎦⎤
对此矩阵快速幂即可
需要注意的是，单位矩阵是主对角线元素为1 1 1的矩阵，其他元素为0 0 0；而不是都是1 1 1的矩阵
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using ll=long long;
const int N=1e6+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+7;
struct matrix
{
ll a[3][3];
void initial(){memset(a,0,sizeof(a));}
void build()
{
initial();
for(int i=0;i<3;i++) a[i][i]=1;
}
ll* operator[](int i) const {
return (ll*)&a[i][0];
}
matrix operator*(const matrix& x) const
{
matrix ret; ret.initial();
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++) ret[i][j]=(ret[i][j]+a[i][k]*x[k][j]%mod)%mod;
return ret;
}
};
matrix qpow(matrix a,ll b)
{
matrix ret,base=a; ret.build();
while(b)
{
if(b&1) ret=ret*base;
base=base*base;
b>>=1;
}
return ret;
}
int main()
{
matrix tmp={{
{1,1,0},
{0,0,1},
{1,0,0}
}},ans={{
{1,1,1},
{0,0,0},
{0,0,0}
}};
int t; cin>>t;
while(t--)
{
ll n; cin>>n;
if(n3) cout<<1<<'\n';
else cout<<(ans*qpow(tmp,n-3)).a[0][0]<<'\n';
}
return 0;
}
Original: https://blog.csdn.net/stdforces/article/details/127826481
Author: stdforces
Title: 洛谷P1939 矩阵快速幂模板
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/661103/
转载文章受原作者版权保护。转载请注明原作者出处！