首页 > 代码库 > Hdu5015 (233 Matrix)
Hdu5015 (233 Matrix)
这题是今年西安网络赛的一题,当时真是想不出来,竟然在推第n行m列的通项公式...后来被学长A掉,说是矩阵快速幂,于是赶紧脑补了一下。
我现在理解的大概就是构造前一个矩阵,一般是一行的,是初始的信息,比如斐波纳契数列的(f[2] f[1]),然后成上一个方阵,这个方阵也需要根据不同的题进行构造,要求就是初始的那个矩阵在经过第二个矩阵的右乘之后可以递推到下一个式子并保持可以更新的状态.
在斐波纳契数列中,右乘的方阵是
( 1 1
1 0)
乘之后前一个矩阵就变成 (f[3] f[2]) 要求第n项就是把这个方阵做快速幂然后用结果方阵乘初始矩阵.
跑题了。
我这个题的初始矩阵是(233 3 a1 a2...an)
方阵是
( 10 0 1 1 ...
1 1 0 0
0 0 1 1
0 0 0 1
. . . .
0 0 0 0)
AC代码
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <stdlib.h> 5 #define maxn 15 6 #define MOD 10000007 7 using namespace std; 8 class Matrix{ 9 public:10 int row,col;11 __int64 mapp[maxn][maxn];12 Matrix(int r,int c):row(r),col(c){}13 Matrix(){}14 void ini()15 {16 memset(mapp,0,sizeof(mapp));17 for(int i=2;i<row;i++)18 {19 mapp[0][i]=1;20 for(int j=i;j<row;j++)21 mapp[i][j]=1;22 }23 mapp[0][0]=10,mapp[1][0]=1,mapp[1][1]=1;24 }25 void unit() //单位矩阵的初始化26 {27 memset(mapp,0,sizeof(mapp));28 for(int i=0;i<row;i++)29 mapp[i][i]=1;30 }31 int result(int which) const{return mapp[0][which];}32 friend Matrix operator*(const Matrix&,const Matrix&);33 void Pow(int);34 };35 Matrix operator*(const Matrix& M1,const Matrix& M2)36 {37 Matrix M(M1.row,M2.col);38 for(int i=0;i<M1.row;i++)39 for(int j=0;j<M2.col;j++)40 {41 M.mapp[i][j]=0;42 for(int k=0;k<M2.col;k++)43 M.mapp[i][j]=(M.mapp[i][j]+M1.mapp[i][k]*M2.mapp[k][j])%MOD;44 }45 return M;46 }47 Matrix M;48 int N;49 void Matrix::Pow(int n)//矩阵快速幂50 {51 //cout<<n<<endl;52 Matrix temp(N+2,N+2);53 temp.ini();54 while(n)55 {56 if(n&1)57 M=M*temp;58 temp=temp*temp;59 n>>=1;60 }61 }62 int main()63 {64 int m;65 while(~scanf("%d%d",&N,&m))66 {67 Matrix resM(1,N+2);68 M.row=M.col=N+2;69 M.unit();70 resM.mapp[0][0]=233,resM.mapp[0][1]=3;71 for(int i=1;i<=N;i++) scanf("%I64d",&resM.mapp[0][i+1]);72 M.Pow(m);73 resM=resM*M;74 cout<<resM.result(N+1)<<endl;75 }76 return 0;77 }
Hdu5015 (233 Matrix)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。