矩阵快速幂（模板+构造）
矩阵快速幂（模板+构造）
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007
/* ( x x x x x )^n
( x x x x x )
(x x x x x) * ( x x x x x )
( x x x x x )
( x x x x x ) */
LL nn;
struct mat{
LL m[10][10];
};
mat matmul(mat a,mat b){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=nn;i++){
for(int j=1;j<=nn;j++){
for(int k=1;k<=nn;k++){
re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return re;
}
mat quickmod(LL x,mat jin){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=nn;i++) re.m[i][i]=1;
while(x){
if(x&1)
re=matmul(re,jin);
x=x>>1;
jin=matmul(jin,jin);
}
return re;
}
mat init(){
mat x;
memset(re.m,0,sizeof(re.m));
......
return x;
}
int main(){
nn=...;
mat t=quickmod(.init());
x=matmul(x,t);
cout.....
return 0;
}先写出递推式，写出前一项或者后一项，然后发现所有的关键要素（递推式的不是相邻项，要把中间的项考虑进去），然后根据递推式写出矩阵。思路理清楚，处理好边界，处理好细节。（我喜欢多些一维，好理解，其实写多了都可以省掉）
http://www.51nod.com/Challenge/Problem.html#!#problemId=1126
1126 求递推序列的第N项
- 1 秒
- 131,072 KB
- 10 分
- 2 级题
有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A，B和N，求f(n)的值。
输入
输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)输出
输出f(n)的值。输入样例
3 -1 5输出样例
6
类似斐波那契。注意负数取余要加上mod再%mod。
#include <iostream>
using namespace std;
int n;
struct mat{
int a[2][2];
};
mat matmul(mat x,mat y){
mat z;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
z.a[i][j]=((x.a[0][j]*y.a[i][0]+x.a[1][j]*y.a[i][1])%7+7)%7;
}
}
return z;
}
mat matpow(mat x,mat y){
while(n>0){
if(n&1){
y=matmul(x,y);
}
n=n/2;
x=matmul(x,x);
}
return y;
}
int main(){
int A,B;
cin >> A >> B >> n;
mat re,c;
n=n-2;
c.a[0][0]=A;c.a[0][1]=1;
c.a[1][0]=B;c.a[1][1]=0;
re.a[0][0]=1;re.a[0][1]=0;
re.a[1][0]=0;re.a[1][1]=1;
re=matpow(c,re);
cout << ((re.a[0][0]+re.a[1][0])%7+7)%7;
return 0;
} http://codeforces.com/contest/1117/problem/D
递推式：f(n)=f(n-1)+..+f(n-m)。
（多算了一维，好理解）
注意处理n<m。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define mod 1000000007
#define N 105
/* ( x x x x x )^n
( x x x x x )
(x x x x x) * ( x x x x x )
( x x x x x )
( x x x x x ) */
LL n,m;
struct mat{
LL m[N][N];
};
mat matmul(mat a,mat b){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=m+1;i++){
for(int j=1;j<=m+1;j++){
for(int k=1;k<=m+1;k++){
re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return re;
}
mat quickmod(LL x,mat jin){
mat re;
for(int i=1;i<=m+1;i++) re.m[i][i]=1;
while(x){
if(x&1)
re=matmul(re,jin);
x=x>>1;
jin=matmul(jin,jin);
}
return re;
}
mat init(){
mat x;
memset(x.m,0,sizeof(x.m));
x.m[1][1]=1;x.m[m][1]=1;
for(int i=1;i<=m;i++){
x.m[i][i+1]=1;
}
return x;
}
int main(){
cin>>n>>m;
if(n<m) {
cout<<1;
return 0;
}
mat t;
memset(t.m,0,sizeof(t.m));
for(int i=1;i<=m+1;i++)
t.m[1][i]=1;
t.m[1][1]++;
mat mm=quickmod(n-m,init());
mm=matmul(t,mm);
cout<<mm.m[1][1];
return 0;
}http://acm.hdu.edu.cn/showproblem.php?pid=5950
递推式：f(n)=f(n-1)+2*f(n-2)+i^4。
递推下一项是f(n+1)=f(n)+2*f(n-1)+(i+1)^4。
将上式展开，发现与连续三项有关，与i^4,i^3,i^2,i^1,i^0，有关。
然后推矩阵（多一维）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define mod 2147493647
#define N 20
/* ( x x x x x )^n
( x x x x x )
(x x x x x) * ( x x x x x )
( x x x x x )
( x x x x x ) */
LL nn;
struct mat{
LL m[10][10];
};
mat matmul(mat a,mat b){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=nn;i++){
for(int j=1;j<=nn;j++){
for(int k=1;k<=nn;k++){
re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
}
}
}
return re;
}
mat quickmod(LL x,mat jin){
mat re;
memset(re.m,0,sizeof(re.m));
for(int i=1;i<=nn;i++) re.m[i][i]=1;
while(x){
if(x&1)
re=matmul(re,jin);
x=x>>1;
jin=matmul(jin,jin);
}
return re;
}
mat init(){
mat x;
x.m[1][1]=1;x.m[1][2]=1;x.m[1][3]=0;x.m[1][4]=0;x.m[1][5]=0;x.m[1][6]=0;x.m[1][7]=0;x.m[1][8]=0;
x.m[2][1]=2;x.m[2][2]=0;x.m[2][3]=1;x.m[2][4]=0;x.m[2][5]=0;x.m[2][6]=0;x.m[2][7]=0;x.m[2][8]=0;
x.m[3][1]=0;x.m[3][2]=0;x.m[3][3]=0;x.m[3][4]=0;x.m[3][5]=0;x.m[3][6]=0;x.m[3][7]=0;x.m[3][8]=0;
x.m[4][1]=1;x.m[4][2]=0;x.m[4][3]=0;x.m[4][4]=1;x.m[4][5]=0;x.m[4][6]=0;x.m[4][7]=0;x.m[4][8]=0;
x.m[5][1]=4;x.m[5][2]=0;x.m[5][3]=0;x.m[5][4]=4;x.m[5][5]=1;x.m[5][6]=0;x.m[5][7]=0;x.m[5][8]=0;
x.m[6][1]=6;x.m[6][2]=0;x.m[6][3]=0;x.m[6][4]=6;x.m[6][5]=3;x.m[6][6]=1;x.m[6][7]=0;x.m[6][8]=0;
x.m[7][1]=4;x.m[7][2]=0;x.m[7][3]=0;x.m[7][4]=4;x.m[7][5]=3;x.m[7][6]=2;x.m[7][7]=1;x.m[7][8]=0;
x.m[8][1]=1;x.m[8][2]=0;x.m[8][3]=0;x.m[8][4]=1;x.m[8][5]=1;x.m[8][6]=1;x.m[8][7]=1;x.m[8][8]=1;
return x;
}
int main(){
int T;cin>>T;
while(T--){
LL n,a,b;
cin>>n>>a>>b;
if(n==1) {cout<<a<<endl;continue;}
if(n==2) {cout<<b<<endl;continue;}
nn=8;
mat x;memset(x.m,0,sizeof(x.m));
x.m[1][1]=(2*a+b+81)%mod;x.m[1][2]=b;x.m[1][3]=a;x.m[1][4]=81;x.m[1][5]=27;x.m[1][6]=9;x.m[1][7]=3;x.m[1][8]=1;
mat t=quickmod(n-3,init());
x=matmul(x,t);
cout<<x.m[1][1]<<endl;
}
return 0;
}