矩阵乘法
设一个(n*m)的矩阵A，一个(m*p)的矩阵B。那么A*B的结果设为C，是一个(n*p)的矩阵
相乘的方式是拿出A矩阵的第i行和B矩阵的第j列，每个元素对应相乘再相加，放到C矩阵的(i,j)这个位置
显然只有前一个矩阵的列数和后一个矩阵的行数相同，它们才可以相乘
栗子
单位矩阵
(n)阶单位矩阵，是一个 (n imes n) 的方形矩阵，其主对角线元素为1，其余元素为0。单位矩阵以(I_{n})表示；如果阶数可忽略，或可由前后文确定的话，也可简记为I（或者E）。
——---维基百科
显得肥肠鸡肋啊，然鹅满足结合律的它可以优化dpT1
m次询问，求Fibonacci数列的第n项
pts1. (m=1,n=1000000)
pts2. (m=1000000,n=1000000)
pts3. (m=1000,n=1000000000)
直接说3吧
递推式 (f_i=f_{i-1}+f_{i-2})，然后时间就炸了
矩阵优化！
((i-1,i)) 表示第(i)项和第(i-1)项，那么转移时只要乘上(egin{pmatrix}0 & 1\ 1 & 1end{pmatrix})即可
所以第i项就是((1,1)*egin{pmatrix}0 & 1\ 1 & 1end{pmatrix}^{i-2})的第二项，快速幂优化即可
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 1000000007
using namespace std;
long long i,m,n,j,k,b[2][2],t;
struct vv
{
long long d[2][2];
} a,tmp,c;
vv cheng(vv a,vv b,long long x,long long y,long long t)
{
vv g;
memset(g.d,0,sizeof(g.d));
for(long long i=0;i<x;i++)
for(long long j=0;j<y;j++)
for(long long k=0;k<t;k++) g.d[i][j]=(g.d[i][j]+(a.d[i][k]*b.d[k][j])%M)%M;
return g;
}
vv ksm(long long k)
{
vv x,y;
x.d[0][0]=0; x.d[0][1]=1; x.d[1][0]=1; x.d[1][1]=1;
y.d[0][0]=1; y.d[1][1]=1; y.d[1][0]=0; y.d[0][1]=0;
//k-=1;
for(;k>1;k>>=1)
{
if(k&1) y=cheng(y,x,2,2,2);
x=cheng(x,x,2,2,2);
}
return cheng(x,y,2,2,2);
}
int main()
{
scanf("%d",&t);
for(;t;t--)
{
scanf("%lld",&n);
if(n<=2)
{
printf("1");
return 0;
}
a=ksm(n-2);
c.d[0][0]=c.d[0][1]=1;
c=cheng(c,a,1,2,2);
printf("%lld",c.d[0][1]);
}
}
栗2
题目大意
一个长度为n的1,0串组成环，其中不能有两个0相连。
设(f[i][0/1])表示第i位为0或1的情况数，那么
(left{egin{matrix}
f[i][0]=f[i-1][1] & \
f[i][1]=f[i-1][0]+f[i-1][1] &
end{matrix}
ight.)
然后列出矩阵(egin{pmatrix} 0 & 1\ 1 & 1 end{pmatrix})
Fibonacci数列....
然后对于每一个询问假设第一位为1，求出第n位1+0的和，假设第1位为0求第n位1的个数，所以带入((1,1))求第n-2项1*2+0即可
一定要记得特判记得特判记得特判.....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define max(a,b) ((a)>(b) ? (a): (b))
#define min(a,b) ((a)<(b) ? (a): (b))
#define M 1000000007
#define LL long long
using namespace std;
LL i,m,n,j,k;
struct vv
{
LL g[3][3];
} f,d,w;
vv cheng(vv a,vv b,LL n,LL m,LL z)
{
vv o;
memset(o.g,0,sizeof(o.g));
for(LL i=0;i<n;i++)
for(LL j=0;j<m;j++)
for(LL l=0;l<z;l++)
o.g[i][j]=(o.g[i][j]+a.g[i][l]*b.g[l][j]%M)%M;
return o;
}
vv ksm(LL x)
{
vv w;
memset(w.g,0,sizeof(w.g));
for(LL i=0;i<2;i++) w.g[i][i]=1;
for(;x>1;x>>=1)
{
if(x&1) w=cheng(w,f,2,2,2);
f=cheng(f,f,2,2,2);
}
return cheng(f,w,2,2,2);
}
int main()
{
scanf("%lld",&m);
for(m;m;m--)
{
scanf("%lld",&n);
if(n==1) {printf("1
"); continue;}
f.g[0][0]=0; f.g[0][1]=1;
f.g[1][1]=1; f.g[1][0]=1;
d.g[0][0]=0; d.g[0][1]=1;
vv t=cheng(d,ksm(n-1),1,2,2);
printf("%lld
",(t.g[0][0]*2+t.g[0][1])%M);
}
}
新芝士 循环矩阵！
就是矩阵的每一行是上一行右移一位
循环矩阵+循环矩阵还是循环矩阵
循环矩阵*循环矩阵还是循环矩阵
https://www.lydsy.com/JudgeOnline/problem.php?id=1898
http://acm.hdu.edu.cn/showproblem.php?pid=2604