233 Matrix 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 1
1
2 2
0 0
3 7
23 47 16

Sample Output

234
2799
72937

Hint

---

题意:

根据题目给的递推式计算二维矩阵最右下角的那一个值.

思路:

矩阵快速幂.根据递推式$a_{i,j} = a_{i, j - 1} + a_{i-1,j} $ 而且矩阵的第一行是数 $a_{1,j} = a_{1,j-1} * 10 + 3$,那么我们在二维矩阵的上面再加一行,这一行的每一个数都是 3 .由此我们可以构造出递推矩阵.具体矩阵构造请看代码.

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;

typedef long long LL;
const int mod = 10000007;
LL n,m;
LL b[20];

struct mat{
    LL a[20][20];
    mat(){ memset(a, 0, sizeof(a));}
    mat operator *(const mat q){
        mat c;
        for(int  i = 1; i <=n; ++i)
            for(int k = 1; k <= n;++k)
            if(a[i][k])
        for(int  j = 1; j <= n; ++j){
            c.a[i][j] += a[i][k] * q.a[k][j];
            if(c.a[i][j] >= mod)
                c.a[i][j] %= mod;
        }return c;
    }
};

mat qpow(mat x, LL k){
    mat ans;
    for(int i = 0; i<= 15;++i)
        ans.a[i][i] = 1;
    while(k){
        if(k&1) ans =  ans * x;
        x = x * x;
        k >>= 1;
    }return ans;
}

int main(){
    mat x; 
    for(int i = 1 ;i <= 15; ++i)
    for(int j = 1; j <= i; ++j){
        x.a[i][j] = 1;
        if(j == 2)
            x.a[i][j] = 10;
    }
    while(scanf("%I64d %I64d", &n, &m) != EOF){
        n += 2; b[1] = 3; b[2] = 23;
        for(int i = 3; i <= n; ++i)
            scanf("%I64d", &b[i]);
     mat t = qpow(x, m);
     LL ans = 0;
     for(int  i = 1; i <= n; ++i)
         ans = (ans + b[i] * t.a[n][i]) % mod;
     printf("%I64d\n", ans);
    }return 0;
}