首页 > 代码库 > HDU 5015 233 Matrix
HDU 5015 233 Matrix
题意：给定一个矩阵的第0列的第1到n个数，第一行第1个数开始每个数分别为233， 2333........，求第n行的第m个数。
分析：
其实也没那么难，自己想了半天还没往对的方向想，m最大1e9，应该立即想到要用到快速幂，关键在于递推矩阵。
递推矩阵的作用是依次算出每一列，第1列第一个数233是前一列的23*10+3，将前一列增加一个元素[3, 23, a1, a2,....an]，然后第一列第一个数为3，对应向量[1, 0, 0, 0.....0],233对应向量[1, 10, 0, .....0]，下一个的数对应[1, 10, 1.....0]， 接下来每个数对应的向量是上一个数的向量最后一个1元素后面增加1个1，这样将n+2个向量构成一个(n+2)*(n+2)的矩阵，需要求m次该矩阵，然后和[3, 23, a1, a2, .....an]相乘。
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <vector> 4 #include <algorithm> 5 #define inf 0x0f0f0f0f 6 #define pb push_back 7 #define bug(x) printf("line %d: >>>>>>>>>>>>>>>\n", (x)); 8 #define in freopen("F:\\code\\data\\data.txt", "r", stdin); 9 #define out freopen("F:\\code\\data\\data_out.txt", "w", stdout);10 11 #define SZ(x) ((int)x.size())12 #define lson rt<<1, l, m13 #define rson rt<<1|1, m+1, r14 using namespace std;15 16 typedef long long LL;17 const int maxn = 22;18 const int M = 10000007;19 20 struct Matrix21 {22 int n, m;23 LL a[maxn][maxn];24 Matrix(int n, int m)25 {26 this->n = n;27 this->m = m;28 for(int i = 0; i < maxn; i++)29 for(int j = 0; j < maxn; j++)30 a[i][j] = 0;31 }32 Matrix operator * (const Matrix &o)const33 {34 Matrix c(n, o.m);35 for(int i = 0; i < n; i++)36 for(int j = 0; j < o.m; j++)37 {38 for(int k = 0; k < m; k++)39 c.a[i][j] = (c.a[i][j]+a[i][k]*o.a[k][j]%M)%M;40 }41 return c;42 }43 };44 int n, m;45 int main()46 {47 48 while(scanf("%d%d", &n, &m) == 2)49 {50 Matrix f(n+2, n+2), res(n+2, n+2), tmp(n+2, 1);51 tmp.a[0][0] = 3;52 tmp.a[1][0] = 23;53 for(int i = 2; i <= n+1; i++)54 scanf("%I64d", &tmp.a[i][0]);55 for(int i = 0; i <= n+1; i++)56 for(int j = 0; j <= n+1; j++)57 {58 if(i == 0)59 {60 f.a[i][0] = 1;61 break;62 }63 else if(i == 1)64 {65 f.a[i][0] = 1;66 f.a[i][1] = 10;67 break;68 }69 else70 {71 if(j < i)72 f.a[i][j] = f.a[i-1][j];73 else if(j == i) f.a[i][j] = 1;74 }75 }76 for(int i = 0; i < n+2; i++)77 for(int j = 0; j < n+2; j++)78 if(i == j)79 res.a[i][j] = 1;80 while(m)81 {82 if(m&1)83 res = res*f;84 f = f*f;85 m >>= 1;86 }87 tmp = res*tmp;88 printf("%I64d\n", tmp.a[n+1][0]);89 }90 return 0;91 }
HDU 5015 233 Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。