首页 > 代码库 > hdu-5015-233 Matrix-矩阵
hdu-5015-233 Matrix-矩阵
非常显然矩阵的第一列为:
0
a[1]
a[2]
a[3]
a[4]
我们转化一下,转化为
23
a[1]
a[2]
a[3]
a[4]
3
那么由第一列转移到第二列则为
23*10+3
a[1]+23*10+3
a[2]+a[1]+23*10+3
a[3]+a[2]+a[1]+23*10+3
a[4]+a[3]+a[2]+a[1]+23*10+3
3
非常显然转移矩阵A就出来了:
10 0 0 0 0 1
10 1 0 0 0 1
10 1 1 0 0 1
10 1 1 1 0 1
10 1 1 1 1 1
0 0 0 0 0 1
那么最后一列就是A的m次方*第一列。
#include<stdio.h> #include<iostream> #include<stdlib.h> #include<string.h> #include<algorithm> #include<vector> #include<math.h> #include<queue> #include<stack> #include<map> #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define maxn 110000 #define mod 10000007 #define LL __int64 struct matrix { LL mat[15][15]; matrix() { memset(mat,0,sizeof(mat)); } }; int a[11]; int n; matrix mul(matrix A,matrix B) { matrix C; int i,j,k; for(i=1; i<=n+2; i++) { for(j=1; j<=n+2; j++) { for(k=1; k<=n+2; k++) { C.mat[i][j]=(C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod; } } } return C; } matrix powmul(matrix A,int k) { matrix B; for(int i=1;i<=n+2;i++)B.mat[i][i]=1; while(k>=1) { if(k&1)B=mul(B,A); A=mul(A,A); k=k/2; } return B; } void print(matrix A) { cout<<"matrix A"<<endl; for(int i=1;i<=n+2;i++) { for(int j=1;j<=n+2;j++) { cout<<A.mat[i][j]<<" "; } cout<<endl; } } int main() { int m; while(~scanf("%d%d",&n,&m)) { matrix A,B; A.mat[1][1]=23; for(int i=1;i<=n;i++) { scanf("%d",&A.mat[i+1][1]); } A.mat[n+2][1]=3; for(int i=1;i<=n+1;i++)B.mat[i][1]=10; for(int i=1;i<=n+2;i++)B.mat[i][n+2]=1; for(int i=2;i<=n+1;i++) { for(int j=2;j<=i;j++)B.mat[i][j]=1; } // print(A); // print(B); B=powmul(B,m); A=mul(B,A); // print(A); cout<<A.mat[n+1][1]<<endl; } return 0; }
hdu-5015-233 Matrix-矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。