poj3233
经典题
因为k的值太大，如果直接算，肯定会超时。
因此采用二分的方法。
#include <cstdio>
#include <cstring>
using namespace std;
int n,k,m;
struct matrix
{
int mat[35][35];
};
matrix A;
void init(matrix &a)
{
memset(a.mat,0,sizeof(a.mat));
for(int i=1;i<=n;i++)
a.mat[i][i]=1;
}
matrix mul(matrix a,matrix b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int w=1;w<=n;w++)
{
res.mat[i][j]+=((a.mat[i][w]*b.mat[w][j])%m);
res.mat[i][j]%=m;
}
}
}
return res;
}
matrix m_pow(matrix a,int b)
{
matrix res;
init(res);
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
matrix add(matrix a,matrix b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
res.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%m;
}
return res;
}
matrix mat_sum(int p)
{
if(p==1)
return A;
matrix tmp,b;
tmp=mat_sum(p/2);
if(p&1)
{
b=m_pow(A,p/2+1);
tmp=add(tmp,mul(tmp,b));
tmp=add(b,tmp);
}
else
{
b=m_pow(A,p/2);
tmp=add(tmp,mul(tmp,b));
}
return tmp;
}
int main()
{
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
memset(A.mat,0,sizeof(A.mat));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&A.mat[i][j]);
A.mat[i][j]%=m;
}
}
matrix ans=mat_sum(k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j<n)
printf("%d ",ans.mat[i][j]);
else
printf("%d\n",ans.mat[i][j]);
}
}
}
return 0;
}
矩阵运算的加和乘可以通过运算符重载。
也可以用等比矩阵的做法，速度会更快。
构造矩阵大矩阵
| A E|
|0 E|
那么此矩阵的k+1次方的右上方部分就等于要求的答案+E
#include <cstdio>
#include <cstring>
using namespace std;
int n,k,m,maxn;
struct matrix
{
int mat[70][70];
matrix operator *(matrix const &b)const
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=maxn;i++)
{
for(int j=1;j<=maxn;j++)
{
for(int w=1;w<=maxn;w++)
res.mat[i][j]=(res.mat[i][j]+(this->mat[i][w])*b.mat[w][j])%m;
}
}
return res;
}
};
matrix m_pow(matrix a,int b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=maxn;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
maxn=n*2;
matrix A;
memset(A.mat,0,sizeof(A.mat));
//构造矩阵
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&A.mat[i][j]);
A.mat[i][j]%=m;
}
}
for(int i=1;i<=maxn;i++)
{
for(int j=n+1;j<=maxn;j++)
{
if(i<=n)
{
if(i==j-n)
A.mat[i][j]=1;
}
else
{
if(i==j)
A.mat[i][j]=1;
}
}
}
matrix ans=m_pow(A,k+1);
for(int i=1;i<=n;i++)
{
for(int j=n+1;j<=maxn;j++)
{
if(i==j-n)
ans.mat[i][j]-=1;
if(j<maxn)
printf("%d ",(ans.mat[i][j]%m+m)%m);//因为减1,为了防止出现负数
else
printf("%d\n",(ans.mat[i][j]%m+m)%m);
}
}
}
return 0;
}
hdu 1575
模板题
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=9973;
struct matrix
{
int mat[12][12];
};
int n,k;
void init(matrix &a)
{
memset(a.mat,0,sizeof(a.mat));
for(int i=1;i<=n;i++)
a.mat[i][i]=1;
}
matrix mul(matrix a,matrix b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int w=1;w<=n;w++)
{
res.mat[i][j]+=(a.mat[i][w]*b.mat[w][j])%mod;
res.mat[i][j]%=mod;
}
}
}
return res;
}
matrix m_pow(matrix a,int b)
{
matrix res;
init(res);
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
matrix A;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&A.mat[i][j]);
}
matrix ans=m_pow(A,k);
int sum=0;
for(int i=1;i<=n;i++)
{
sum+=ans.mat[i][i];
sum%=mod;
}
printf("%d\n",sum);
}
return 0;
}
矩阵快速幂的应用：
poj3070
题目已经给出了矩阵关系
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=1e4;
typedef long long ll;
struct matrix
{
int mat[5][5];
};
int n;
matrix f;
void init2()
{
f.mat[1][1]=1;
f.mat[1][2]=1;
f.mat[2][1]=1;
f.mat[2][2]=0;
}
void init(matrix &a)
{
memset(a.mat,0,sizeof(a.mat));
for(int i=1;i<=2;i++)
a.mat[i][i]=1;
}
matrix mul(matrix a,matrix b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
for(int k=1;k<=2;k++)
{
res.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]);
res.mat[i][j]%=mod;
}
}
}
return res;
}
matrix m_pow(matrix a,int b)
{
matrix res,base=a;
init(res);
while(b)
{
if(b&1)
res=mul(res,base);
base=mul(base,base);
b>>=1;
}
return res;
}
int main()
{
init2();
while(scanf("%d",&n),n!=-1)
{
if(n==0)
printf("0\n");
else if(n==1)
printf("1\n");
else
{
matrix ans=m_pow(f,n-1);
printf("%d\n",ans.mat[1][1]%mod);
}
}
return 0;
}
hdu1588
基本思路：
首先对于斐波那契数列：
f(n)=
|1 1| ^n 取（1,2）位置处
|1 0|
由此可以得出题目要求的为一个等比数列，利用第一题中等比数列的做法
构造矩阵
|A E|
|0 E|
其中A为公比，最后的前n项和在此构造矩阵进行(n-1)次幂后的(1,2)位置处。
提出公因式，分别求出。
最后相乘即可。
注意数据类型。
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
struct matrix
{
ll mat[6][6];
};
ll M;
matrix A;
void init()
{//构造基本矩阵
memset(A.mat,0,sizeof(A.mat));
A.mat[1][1]=1;
A.mat[1][2]=1;
A.mat[2][1]=1;
}
matrix mul(matrix a,matrix b,int c)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=c;i++)
{
for(int j=1;j<=c;j++)
{
for(int k=1;k<=c;k++)
res.mat[i][j]=(res.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%M)%M;//可能会超int，WA
}
}
return res;
}
matrix m_pow(matrix a,ll b,int c)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=4;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=mul(res,a,c);
a=mul(a,a,c);
b>>=1;
}
return res;
}
int main()
{
init();
ll k,b,n;
while(scanf("%lld%lld%lld%lld",&k,&b,&n,&M)!=EOF)
{
matrix B;
memset(B.mat,0,sizeof(B.mat));
B=m_pow(A,k,2);//A^k
matrix C;
memset(C.mat,0,sizeof(C.mat));
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
if(i<=2&&j<=2)
C.mat[i][j]=B.mat[i][j];
if(j>2)
{
if(i==j)
C.mat[i][j]=1;
if(i==j-2)
C.mat[i][j]=1;
}
}
}
matrix D=m_pow(C,n,4);
memset(B.mat,0,sizeof(B.mat));
for(int i=1;i<=2;i++)
{
for(int j=3;j<=4;j++)
B.mat[i][j-2]=D.mat[i][j];
}
matrix ans;
ans=mul(m_pow(A,b,2),B,2);
printf("%lld\n",ans.mat[1][2]%M);
}
return 0;
}
hdu1757
主要是能够根据题目给的条件构造相应的矩阵
k>=10时：
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll m;
int an[11];
struct matrix
{
ll mat[12][12];
};
matrix mul(matrix a,matrix b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=10;i++)
{
for(int j=1;j<=10;j++)
{
for(int k=1;k<=10;k++)
res.mat[i][j]=(res.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%m)%m;
}
}
return res;
}
matrix m_pow(matrix a,ll b)
{
matrix res;
memset(res.mat,0,sizeof(res.mat));
for(int i=1;i<=10;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
int main()
{
ll k;
while(scanf("%lld%lld",&k,&m)!=EOF)
{
for(int i=0;i<=9;i++)
scanf("%d",&an[i]);
if(k<10)
printf("%lld\n",k%m);
else
{
matrix A;
memset(A.mat,0,sizeof(A.mat));
for(int i=1;i<=10;i++)//构造矩阵
A.mat[1][i]=(an[i-1]%m);
for(int i=2;i<=10;i++)
{
for(int j=1;j<=9;j++)
{
if(i-1==j)
A.mat[i][j]=1;
}
}
matrix f;
memset(f.mat,0,sizeof(f.mat));
for(int i=0;i<=9;i++)
f.mat[i+1][1]=((9-i)%m);
matrix ans=m_pow(A,k-9);
ans=mul(ans,f);
printf("%lld\n",ans.mat[1][1]%m);
}
}
return 0;
}
hdu2254
题目要求求出t1到t2时间内从v1到v2的道路数目，
一开始看题目，觉得和矩阵完全没有关系，后来看了别人的思路才知道有可达矩阵这个东西，离散数学真是白学了。
用A表示一步可达的情况，那么A^n表示n不可达的情况，因此只要求A ^t1+…+A ^t2即可。
显然这是一个部分等比数列求和，直接求一定会tle,因此可以采用本博客第一题中的二分的方法，
也可以用我下面的方法，先求出A^t1，然后一项一项的乘，同时记录下v1到V2的路径数量。
但这样还是会tle(我已经t了好几次)，因此在矩阵相乘的时候要运用一定小技巧（我也是看了别人的代码才知道的），见代码。
还要这样城市的离散化。
这样就能过了。
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=2008;
int cnt;
struct matrix
{
int mat[35][35];
void clc()
{
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
(this->mat[i][j])=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=cnt;i++)
{
for(int k=1;k<=cnt;k++)
{
if(this->mat[i][k])//减少运算次数
for(int j=1;j<=cnt;j++)
res.mat[i][j]=(res.mat[i][j]%mod+(this->mat[i][k])*b.mat[k][j]%mod)%mod;
}
}
return res;
}
};
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=cnt;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
map<ll,int>mp;
matrix A;
A.clc();
cnt=0;
ll a,b;//构造矩阵
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&a,&b);
if(!mp[a])
mp[a]=(++cnt);
if(!mp[b])
mp[b]=(++cnt);
A.mat[mp[a]][mp[b]]++;
}
int t;
scanf("%d",&t);
ll v1,v2;
int t1,t2;
while(t--)
{
scanf("%lld%lld%d%d",&v1,&v2,&t1,&t2);
if(!mp[v1]||!mp[v2]||(t1==0&&t1==t2)||t1>t2)
{
puts("0");
continue;
}
int x=mp[v1];
int y=mp[v2];
matrix tmp=m_pow(A,t1);
int ans=0;
if(t1>0)
ans=tmp.mat[x][y];
for(int j=t1+1;j<=t2;j++)
{
tmp=tmp*A;
ans=(ans+tmp.mat[x][y])%mod;
}
printf("%d\n",ans%mod);
}
}
return 0;
}
hdu2256
看到这个题目还是发现不了他和矩阵之间的关系，看了别人的推导后才明白过来。
别的地方扣过来的图。
最后的操作真的难想到，如果直接用An+Bn*6^1/2,转化为int 类型，由于浮点数取整的问题，会出现错误。
因为最后取模的数是不大于原数的最大整数去取模，而(5-6^1/2) ^n是小于1的数，2An是一个整数，所有最后结果一定在2An-1和2An之间，直接取2An-1即可。
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int mod=1024;
struct matrix
{
int mat[4][4];
void clc()
{
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
(this->mat[i][j])=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
for(int k=1;k<=2;k++)
res.mat[i][j]=(res.mat[i][j]+(this->mat[i][k]*b.mat[k][j])%mod)%mod;
}
}
return res;
}
};
void init1(matrix &a)
{
a.clc();
a.mat[1][1]=5;
a.mat[1][2]=12;
a.mat[2][1]=2;
a.mat[2][2]=5;
}
void init2(matrix &b)
{
b.clc();
b.mat[1][1]=1;
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=2;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
int T,n;
scanf("%d",&T);
matrix A;
init1(A);
matrix B;
init2(B);
while(T--)
{
scanf("%d",&n);
matrix ans=m_pow(A,n);
ans=ans*B;
int tmp=2*ans.mat[1][1]-1;
//int tmp=(ans.mat[1][1]%mod)+(ans.mat[2][1]%mod)*sqrt(6.0);
printf("%d\n",tmp%mod);
}
return 0;
}
hdu2276
难点还是在于如何构造矩阵，因为某一个时刻的灯的状态取决于它上一秒的状态和它左边的灯的状态，因此可以构造一个矩阵使得对于每一行i，这一行的第j列为1，它的上一列为1，（如果是第一行就最后一列为1），这样，只要在矩阵快速幂的同时对2取模即可知道它在m秒的状态。
#include <cstdio>
#include <cstring>
using namespace std;
int cnt;
struct matrix
{
int mat[105][105];
void clc()
{
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=100;i++)
{
for(int k=1;k<=100;k++)
{
if(this->mat[i][k])
{
for(int j=1;j<=100;j++)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*b.mat[k][j]%2)%2;
}
}
}
return res;
}
};
void init(matrix &a)
{//构造矩阵
a.clc();
for(int i=1;i<=cnt;i++)
{
a.mat[i][i]=1;
if(i==1)
a.mat[cnt][i]=1;
else
a.mat[i-1][i]=1;
}
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=100;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
int m;
matrix A;
while(scanf("%d",&m)!=EOF)
{
getchar();
char T[105];
char c;
cnt=0;
while(scanf("%c",&c),c!='\n')
T[++cnt]=c;//printf("cnt=%d\n",cnt);
init(A);
matrix B;
B.clc();
for(int i=1;i<=cnt;i++)//构造矩阵
B.mat[1][i]=T[i]-'0';
matrix tmp=m_pow(A,m);
matrix ans=B*tmp;
for(int i=1;i<=cnt;i++)
printf("%d",ans.mat[1][i]%2);
printf("\n");
}
return 0;
}
hdu2294
dp+矩阵快速幂优化
hdu2604
递推关系：
f[n]=f[n-1]+f[n-3]+f[n-4]
#include <cstdio>
#include <cstring>
using namespace std;
int m;
struct matrix
{
int mat[6][6];
void clc()
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
for(int k=1;k<=4;k++)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*b.mat[k][j]%m)%m;
}
}
return res;
}
};
void init1(matrix &a)
{
a.clc();
for(int i=1;i<=4;i++)
{
if(i==1)
{
a.mat[1][1]=1;
a.mat[1][3]=1;
a.mat[1][4]=1;
}
else
a.mat[i][i-1]=1;
}
}
void init2(matrix &b)
{
b.clc();
b.mat[1][1]=6;
b.mat[2][1]=4;
b.mat[3][1]=2;
b.mat[4][1]=1;
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=4;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
int l;
matrix A;
init1(A);
matrix B;
init2(B);
while(scanf("%d%d",&l,&m)!=EOF)
{
if(l<=3)
printf("%d\n",B.mat[4-l][1]%m);
else
{
matrix tmp=m_pow(A,l-3);
tmp=tmp*B;
printf("%d\n",tmp.mat[1][1]%m);
}
}
return 0;
}
hdu2855
二项式定理+斐波那契数列
题目要求一个加了组合数的斐波那契。
二项式展开：
(a+b)^n=C(n,0)a ^0b ^n+…+C(n,n)a ^nb ^0。
当我们把展开式中的a换成矩阵A以后，就是题目要求的。
因此就等于(A+E)^n,直接用快速幂模板即可，最后结果为mat[1][2]。
#include <cstdio>
#include <cstring>
using namespace std;
int m;
struct matrix
{
int mat[4][4];
void clc()
{
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
for(int k=1;k<=2;k++)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*b.mat[k][j]%m)%m;
}
}
return res;
}
};
void init(matrix &a)
{
a.clc();
a.mat[1][1]=2;
a.mat[1][2]=1;
a.mat[2][1]=1;
a.mat[2][2]=1;
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=2;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
int t,n;
scanf("%d",&t);
matrix A;
init(A);
while(t--)
{
scanf("%d%d",&n,&m);
matrix ans=m_pow(A,n);
printf("%d\n",ans.mat[1][2]%m);
}
return 0;
}
hdu3483
看完题目，一脸懵逼，毫无思路。
虽然知道要用矩阵快速幂，但不知道怎么构造矩阵。
首先，令f[n]={x^n,nx ^n,…,(n ^x)(x ^n)}。
f[n][k]=(n^k)(x ^n)。
g[n]=f[1][x]+f[2][x]+…+f[n][x],即要求的答案。
又有：
f[n+1][k]=( (n+1)^k * x ^(n+1) )=x((n+1)^k x^n) (n+1)^k可以用二项式展开
=x(c(k,0)x^n+c(k,1)*n x ^ n+…+c(k,k)n^kx ^n)
=x(c(k,0)*f[n][0]+c(k,1)*f[n][1]+…+c(k,k)*f[n][k])
所以可以构造矩阵
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll m,n;
int x;
ll c[52][52];
struct matrix
{
ll mat[55][55];
void clc()
{
for(int i=1;i<=52;i++)
for(int j=1;j<=52;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=52;i++)
{
for(int k=1;k<=52;k++)
{
if(this->mat[i][k])
{
for(int j=1;j<=52;j++)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*b.mat[k][j]%m)%m;
}
}
}
return res;
}
};
void init(matrix &a)
{
memset(c,0,sizeof(c));
for(int i=0;i<=x;i++)
{
c[i][0]=1;
c[i][i]=1;
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]%m+c[i-1][j]%m)%m;
}
a.clc();
for(int i=1;i<=x+1;i++)
{
for(int j=1;j<=i;j++)
a.mat[i][j]=x*c[i-1][j-1]%m;
}
a.mat[x+2][x+1]=1;
a.mat[x+2][x+2]=1;
}
matrix m_pow(matrix a,ll b)
{
matrix res;
res.clc();
for(int i=1;i<=52;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
while(scanf("%lld%d%lld",&n,&x,&m),n>=0||x>=0||m>=0)
{
matrix A;
init(A);
matrix B;
B.clc();
for(int i=1;i<=x+1;i++)
B.mat[i][1]=x;
B.mat[x+2][1]=1;
matrix tmp=m_pow(A,n);
tmp=tmp*B;
printf("%lld\n",(tmp.mat[x+2][1]-1)%m);//减1是因为多算了g[0]=1.
}
return 0;
}
hdu3658
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int m;
struct matrix
{
ll mat[55][55];
void clc()
{
for(int i=1;i<=52;i++)
for(int j=1;j<=52;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=52;i++)
{
for(int k=1;k<=52;k++)
{
if(this->mat[i][k])
{
for(int j=1;j<=52;j++)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*b.mat[k][j]%mod)%mod;
}
}
}
return res;
}
};
void init1(matrix &a)
{
a.clc();
for(int i=1;i<=52;i++)
{
if(i<=26)
{
for(int j=1;j<=i+26;j++)
a.mat[i][j]=1;
}
else
{
for(int j=i-26;j<=52;j++)
a.mat[i][j]=1;
}
}
}
void init2(matrix &b)
{
b.clc();
for(int i=1;i<=52;i++)
{
if(i<=26)
{
for(int j=1;j<=i+25;j++)
b.mat[i][j]=1;
}
else
{
for(int j=i-25;j<=52;j++)
b.mat[i][j]=1;
}
}
}
void init3(matrix &c)
{
c.clc();
for(int i=1;i<=52;i++)
c.mat[i][1]=1;
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=52;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
matrix A;
init1(A);
matrix B;
init2(B);
matrix C;
init3(C);
while(t--)
{
scanf("%d",&m);
matrix tmp1=m_pow(A,m-1)*C;
matrix tmp2=m_pow(B,m-1)*C;
ll ans1=0,ans2=0;
for(int i=1;i<=52;i++)
ans1=(ans1+tmp1.mat[i][1]%mod)%mod;
for(int i=1;i<=52;i++)
ans2=(ans2+tmp2.mat[i][1]%mod)%mod;
printf("%lld\n",(ans1-ans2+mod)%mod);
}
return 0;
}
hdu4565
和hdu2256是同一类型的题目
这种类型的题目，如果要对浮点数进行取整，一定不能直接取，这样一定会错。
要利用某种关系，把它直接转化为整数。
好像都要利用共轭矩阵，然后相加，结果为整数，一个为小于1的小数，那么就可以直接用整数结果来取代另一个浮点数。
推导如下：（有些凌乱）
这种题，以后应该就是套路了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a,b,n,m;
struct matrix
{
int mat[3][3];
void clc()
{
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
for(int k=1;k<=2;k++)
res.mat[i][j]=(res.mat[i][j]+this->mat[i][k]*b.mat[k][j]%m)%m;
}
}
return res;
}
};
void init(matrix &aa)
{
aa.clc();
aa.mat[1][1]=(2*a)%m;
aa.mat[1][2]=(b-a*a+m)%m;
aa.mat[2][1]=1;
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=2;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
while(scanf("%d%d%d%d",&a,&b,&n,&m)!=EOF)
{
matrix A;
init(A);
matrix B;
B.clc();
B.mat[1][1]=(2*a)%m;
B.mat[2][1]=2;
matrix ans=m_pow(A,n-1);
ans=ans*B;
printf("%d\n",(ans.mat[1][1]+m)%m);//wa，防止出现负数
}
return 0;
}
hdu5015
推荐一篇博客，上面讲的很清楚
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=10000007;
int n,m;
struct matrix
{
int mat[14][14];
void clc()
{
for(int i=1;i<=n+2;i++)
for(int j=1;j<=n+2;j++)
this->mat[i][j]=0;
}
matrix operator *(const matrix &b)const
{
matrix res;
res.clc();
for(int i=1;i<=n+2;i++)
{
for(int k=1;k<=n+2;k++)
{
if(this->mat[i][k])
{
for(int j=1;j<=n+2;j++)
res.mat[i][j]=(res.mat[i][j]+(long long)this->mat[i][k]*b.mat[k][j]%mod)%mod;//用long long
}
}
}
return res;
}
};
void init(matrix &a)
{
a.clc();
for(int i=1;i<=n+2;i++)
{
if(i<=n)
{
a.mat[i][n+1]=1;
for(int j=1;j<=i;j++)
a.mat[i][j]=1;
}
else
{
a.mat[i][n+2]=1;
if(i==n+1)
a.mat[i][i]=10;
}
}
}
matrix m_pow(matrix a,int b)
{
matrix res;
res.clc();
for(int i=1;i<=n+2;i++)
res.mat[i][i]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
matrix A;
init(A);
matrix B;
B.clc();
int aa;
for(int i=1;i<=n;i++)
{
scanf("%d",&aa);
B.mat[i][1]=aa;
}
B.mat[n+1][1]=233;
B.mat[n+2][1]=3;
matrix ans=m_pow(A,m);
ans=ans*B;
printf("%d\n",ans.mat[n][1]%mod);
}
return 0;
}
花式矩阵乘法
矩阵乘法的题目基本也做的差不多，但真正能自己推导出递推关系，并且构造出关系矩阵的不多，主要还是利用题目的条件，通过各种方法，弄出一个递推式，然后放在矩阵当中处理，有时候可能要矩阵的几项求和才能得到答案。还是要多做题，积累经验。
还有：矩阵相乘的地方任意爆 int，要注意
京公网安备 11010502036488号