HDU-5015 233 Matrix题解(矩阵快速幂)

Description

传送门:HDU-5015

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})\).

Output

For each case, output \(a_{n,m}\) mod 10000007.

Sample Input

1
2
3
4
5
6
1 1
1
2 2
0 0
3 7
23 47 16

Sample Output

1
2
3
234
2799
72937

题目大意

给你一个矩阵,\(a_{0,0} = 0,a_{0,1} = 233,a_{0,2} = 2333 \cdots\),依次类推,矩阵其他元素的递推公式为\(a_{i,j} = a_{i-1,j} + a_{i,j-1}\),现在给出第一列除第一项之外的数,\(a_{1,0},a_{2,0},a_{3,0},\cdots a_{n,0}\)等,现在求\(a_{n,m}\)

思路

首先我们看第一行的规律,很容易可以发现除了第一项之外,其他项都是\(a_{0,i} = a_{0,i-1}*10+3\),那么我们可以让\(a_{0,0}=23\),再根据\(a_{i,j} = a_{i-1,j} + a_{i,j-1}\)我们可以推出一个转移矩阵。 \[ \begin{bmatrix} 10 & 0 & 0 & \cdots & 3 \\ 10 & 1 & 0 & \cdots & 3 \\ 10 & 1 & 1 & \cdots & 3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 10 & 1 & 1 & \cdots & 3 \\ 0 & 0 & 0 & \cdots & 1 \end{bmatrix} * \begin{bmatrix} a_{0,i}\\ a_{1,i}\\ a_{2,i}\\ \vdots\\ a_{n,i}\\ 1 \end{bmatrix} = \begin{bmatrix} a_{0,i+1}\\ a_{1,i+1}\\ a_{2,i+1}\\ \vdots\\ a_{n,i+1}\\ 1 \end{bmatrix} \] 这样我们就可以用矩阵快速幂来求解了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/************************************************************
> File Name: 233_Mat.cpp
> Author: TSwiftie
> Mail: 2224273204@qq.com
> Created Time: Fri 08 Nov 2019 12:37:25 PM CST
************************************************************/

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
#define lowbit(x) (x&-x)
#define lc o<<1
#define rc o<<1|1
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
const int MOD = 1e7+7;
const int dir[4][2] = {1,0,-1,0,0,1,0,-1};
const double PI = acos(-1.0);
const double EXP = 1e-8;
struct mat{
ll m[15][15];
mat(){
memset(m,0,sizeof m);
}
};
int n;
mat mul(mat a,mat b){
mat c;
for(int i = 1;i <= n+2;i++)
for(int j = 1;j <= n+2;j++)
for(int k = 1;k <= n+2;k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j])%MOD;
return c;
}
mat ksm(mat a,int b){
mat ans;
for(int i = 1;i <= n+2;i++)
ans.m[i][i] = 1;
while(b){
if(b&1)
ans = mul(ans,a);
a = mul(a,a);
b >>= 1;
}
return ans;
}
int main(void){
int m;
while(~scanf("%d%d",&n,&m)){
mat a,b;
a.m[1][1] = 23;
for(int i = 1;i <= n;i++)
scanf("%lld",&a.m[i+1][1]);
a.m[n+2][1] = 3;
for(int i = 1;i <= n+1;i++)
b.m[i][1] = 10;
for(int i = 1;i <= n+2;i++)
b.m[i][n+2] = 1;
for(int i = 1;i < n+2;i++)
for(int j = 2;j <= i;j++)
b.m[i][j] = 1;
b = ksm(b,m);
a = mul(b,a);
printf("%lld\n",a.m[n+1][1]);
}
return 0;
}

本文标题:HDU-5015 233 Matrix题解(矩阵快速幂)

文章作者:TSwifite

发布时间:2019年11月08日 - 23:11

最后更新:2019年11月08日 - 23:11

原始链接:http://tswiftie.com/HDU-5015-233-Matrix题解-矩阵快速幂/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%