首页 > 其他 > 详细

233 Matrix

时间:2018-01-12 21:47:33      阅读:209      评论:0      收藏:0      [点我收藏+]
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 ai,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?

InputThere 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).OutputFor 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

技术分享图片

 

矩阵快速幂

比较裸 ,首先找到原态和现态的关系,233,2333,23333,23333, 这些数都遵循 a0=a0‘*10+3  ,

a1=a0‘*10+3+a1‘  ;   a2=a0‘*10+3+a1‘+a2‘  ;  a3=a0‘*10+3+a1‘+a2‘+a3‘  ;

即 an=a0‘*10+3+技术分享图片

技术分享图片

 

代码如下:

技术分享图片
#include<iostream>
#include<stdio.h>
#include<cstring>
const int MOD=10000007;
using namespace std;
typedef long long LL;
const int M=15;
struct Matrix{
    LL matrix[M][M];
};
int n;//矩阵的阶数
void init(Matrix &res){
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
            res.matrix[i][j]=0;
        res.matrix[i][i]=1;
    }
}
Matrix multiplicative(Matrix a,Matrix b){
    Matrix res;
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < n ; j++)
            for(int k = 0 ; k < n ; k++)
                res.matrix[i][j] =(res.matrix[i][j]%MOD+a.matrix[i][k]%MOD*b.matrix[k][j]%MOD)%MOD;
return res;
}
Matrix pow(Matrix mx,int m){
    Matrix res,base=mx;
    init(res); //初始为单位矩阵,即除主对角线都是1外,其他都是0
    while(m)
    {
        if(m&1)
            res=multiplicative(res,base);
        base=multiplicative(base,base);
        m>>=1;
    }
    return res;
}
void lk_init(Matrix &b)
{
    for(int i=0;i<n-1;i++)
    {
        b.matrix[i][0]=10;
        b.matrix[i][n-1]=1;
    }
    b.matrix[n-1][n-1]=1;
    for(int i=1;i<n-1;i++)
        for(int j=1;j<=i;j++)
            b.matrix[i][j]=1;
}
int main()
{

    int m,a[M];
    while(~scanf("%d%lld",&n,&m))
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        a[0]=23;
        a[n+1]=3;
        n=n+2;
        Matrix base={0};
        lk_init(base);
        base=pow(base,m);
        LL ans=0;
        for(int i=0;i<n;i++)
            ans=(ans%MOD+base.matrix[n-2][i]%MOD*a[i]%MOD+MOD)%MOD;        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

233 Matrix

原文:https://www.cnblogs.com/lemon-jade/p/8277783.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!