首页 > 代码库 > HDU - 233 Matrix
HDU - 233 Matrix
原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=5015
解题思路：一看到题目，感觉是杨辉三角形，然后用组合数学做，不过没想出来怎么做，后来看数据+递推思想，感觉可能是矩阵快速幂，可惜一直不知道a*10+3的 +3怎么处理，果然还是图样图森破啊！如果矩阵能搞出来的话，后面的就简单了，真可惜一直到比赛结束也没想出来，看来这种矩阵的题目做的太少了，真后悔线性代数没有认真学。。
今天晚上又想了一会，完全可以把+3那个放到新的一阶矩阵上，值始终等于3，那么对于233->2333->23333就可以得到矩阵：
1 0
1 10
把这个矩阵和（3,233）相乘就可以得到（3,2333），再乘就得到（3,23333）依次类推。
对于题目中的n，可以构造一个(n+2)*(n+2)的矩阵，可以推出递推矩阵：
1 0 0 0 0.....
1 10 0 0 0...
1 10 1 0 0...
1 10 1 1 0 ...
1 10 1 1 1 ...
前i行的后(i-1)个元素都是0，从第2行开始的每一行的第二个元素都是10，其他都是1。
然后把这个矩阵求p次幂，（用矩阵快速幂）再求出初始向量，最后把向量和刚刚的矩阵快速幂结果相乘，取出结果的最后一个数就是答案啦！
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<iostream> 5 #include<algorithm> 6 #define FOR(i,n) for(i=0;i<(n);i++) 7 #define CLR(a) memset(a,0,sizeof(a)) 8 #define CIN(a) scanf("%d",&a) 9 using namespace std; 10 #define N 15 11 #define M 15 12 #define K 6 13 using namespace std; 14 typedef long long ll; 15 struct matrix 16 { 17 ll m[N][M]; 18 int row,col; 19 }; 20 matrix A,B,C,ANS; 21 matrix& matrix_mul(matrix &a,matrix &b,ll p,matrix &ans)//a，b矩阵相乘每个数模p 22 { 23 for(int i=0;i<a.row;i++) 24 for(int j=0;j<b.col;j++) 25 ans.m[i][j]=0; 26 ans.row=a.row; 27 ans.col=b.col; 28 /*for(int i=0;i<a.row;i++) 29 for(int j=0;j<a.col;j++) 30 if(j<a.col-1) 31 printf("%d ",a.m[i][j]); 32 else printf("%d\n",a.m[i][j]); 33 cout<<endl;*/ 34 for(int i=0;i<a.row;i++) 35 for(int k=0;k<a.col;k++) 36 { 37 for(int j=0;j<b.col;j++) 38 ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%p; 39 } 40 return ans; 41 } 42 void print(matrix& a) 43 { 44 printf("->%d %d\n",a.row,a.col); 45 for(int i=0;i<a.row;i++) 46 for(int j=0;j<a.col;j++) 47 if(j<a.col-1) 48 printf("%d ",a.m[i][j]); 49 else printf("%d\n",a.m[i][j]); 50 cout<<endl; 51 } 52 matrix z; 53 matrix &fast_matrixt_mul_mod(matrix &a,int b,ll p,matrix &ans)//矩阵a的b次方模p 54 { 55 for(int i=0;i<N;i++) 56 for(int j=0;j<M;j++) 57 if(i==j)ans.m[i][j]=1; 58 else ans.m[i][j]=0; 59 ans.row=a.row; 60 ans.col=a.col; 61 //cout<<"=="<<endl; 62 while(b) 63 { 64 if(b&1) 65 { 66 b--; 67 ans=matrix_mul(ans,a,p,z);//ans=ans*a%m; 68 } 69 else 70 { 71 b/=2; 72 a=matrix_mul(a,a,p,z);//a=a*a%m; 73 } 74 /*for(int i=0;i<ans.row;i++) 75 for(int j=0;j<ans.col;j++) 76 if(j<ans.col-1) 77 printf("%d ",ans.m[i][j]); 78 else printf("%d\n",ans.m[i][j]); 79 cout<<endl;*/ 80 } 81 return ans; 82 } 83 matrix Mat,vec,ans; 84 #define mod 10000007 85 int main() 86 { 87 int n,p,i,j; 88 while(scanf("%d%d",&n,&p)!=EOF) 89 { 90 vec.row=n+2; 91 vec.col=1; 92 vec.m[0][0]=3; 93 vec.m[1][0]=23; 94 for(i=2;i<=n+1;i++) 95 { 96 scanf("%I64d",&vec.m[i][0]); 97 } 98 Mat.col=Mat.row=n+2; 99 CLR(Mat.m);100 for(i=0;i<=n+1;i++)101 {102 for(j=0;j<=i;j++)103 {104 if(j!=1)Mat.m[i][j]=1;105 else Mat.m[i][j]=10;106 }107 }108 //print(Mat);109 fast_matrixt_mul_mod(Mat,p,mod,ans);110 matrix_mul(ans,vec,mod,Mat);111 //print(Mat);112 printf("%I64d\n",Mat.m[n+1][0]);113 }114 return 0;115 }
HDU - 233 Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。