首页 > 代码库 > ACM学习历程——HDU5015 233 Matrix（矩阵快速幂）（2014陕西网赛）
ACM学习历程——HDU5015 233 Matrix（矩阵快速幂）（2014陕西网赛）
Description
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333...) Besides, in 233 matrix, we got a i,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,...,a n,0, could you tell me a n,m in the 233 matrix?
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).
Output
For each case, output a n,m mod 10000007.
Sample Input
1 112 20 03 723 47 16
Sample Output
234279972937
Hint
这个题目由于m数据范围很大，故不能直接暴力计算。此处采用矩阵乘法，由矩阵乘法可以由每一列得到下一列。然后矩阵的乘法使用快速幂加快计算。
由2333可以由233乘10加3，于是打算构造n+2行的方阵。
大致如下：
10 0 0 0 ……0 1
10 1 0 0 ……0 1
10 1 1 0 ……0 1
……
10 1 1 1 ……1 1
0 0 0 0 ……0 1
而所要求的列矩阵大致如下：
23……3
a 1,0
a 2,0
……
a n,0
3
递推的正确性可以通过计算验证
此处矩阵通过结构体，运算符重载完成。
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#include <set>#include <map>#include <vector>#include <queue>#include <string>#define inf 0x3fffffff#define esp 1e-10#define N 10000007#define LL long longusing namespace std;struct Mat{ LL val[15][15]; int len; Mat operator = (const Mat& a) { for (int i = 0; i < len; ++i) for (int j = 0; j < len; ++j) val[i][j] = a.val[i][j]; len = a.len; return *this; } Mat operator * (const Mat& a) { Mat x; memset(x.val, 0, sizeof(x.val)); x.len = len; for (int i = 0; i < len; ++i) for (int j = 0; j < len; ++j) for (int k = 0; k < len; ++k) if (val[i][k] && a.val[k][j]) x.val[i][j] = (x.val[i][j] + (val[i][k]*a.val[k][j])%N)%N; return x; } Mat operator ^ (const int& a) { int n = a; Mat x, p = *this; memset(x.val, 0, sizeof(x.val)); x.len = len; for (int i = 0; i < len; ++i) x.val[i][i] = 1; while (n) { if (n & 1) x = x * p; p = p * p; n >>= 1; } return x; }};int n, m;LL a[15], ans;void Make(Mat &p){ p.len = n + 2; memset(p.val, 0, sizeof(p.val)); for (int i = 0; i <= n; ++i) p.val[i][0] = 10; for (int i = 0; i <= n+1; ++i) p.val[i][n+1] = 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) p.val[i][j] = 1;}int main(){ //freopen("test.txt", "r", stdin); while (scanf("%d%d", &n, &m) != EOF) { Mat p; Make(p); p = p ^ m; a[0] = 23; a[n+1] = 3; for (int i = 1; i <= n; ++i) scanf("%I64d", &a[i]); ans = 0; for (int i = 0; i <= n+1; ++i) ans = (ans + (p.val[n][i]*a[i])%N)%N; printf("%I64d\n", ans); } return 0;}
ACM学习历程——HDU5015 233 Matrix（矩阵快速幂）（2014陕西网赛）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。