[原创]HDU 5015 233 Matrix 【矩阵快速幂】

2016-07-29 17:50:50 Tabris_ 阅读数：388

博客爬取于2020-06-14 22:44:03
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52067386

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5015

-------------------------------------------.

233 Matrix

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1817 Accepted Submission(s): 1075

Problem 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 a0,1 = 233,a0,2 = 2333,a0,3 = 23333…) Besides, in 233 matrix, we got ai,j = ai-1,j +ai,j-1( i,j ≠ 0). Now you have known a1,0,a2,0,…,an,0, could you tell me an,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 ≤ 109). The second line contains n integers, a1,0,a2,0,…,an,0(0 ≤ ai,0 < 231).

Output
For each case, output an,m mod 10000007.

Sample Input
1 1
1
2 2
0 0
3 7
23 47 16

Sample Output
234
2799
72937

Hint

-----------------------------------------------------.

题目大意 : 这道题很好读懂不需要翻译

解题思路:
就是构造矩阵然后计算a[n][m]的值

我的思路就是
先把a[i][0]都为0的时候a[n][m]的值计算出来
再把a[0][i]都当成0的时候a[n][m]的值计算出来
把两者相加就是最终的结果了

所以我们就把这个问题分成两个子问题做就是了

一、
我先求的是a[0][i]都当成0的时候的a[n][m]值
这个其实很好求先手写了一下发现有个规律

为了能明确的表达这个规律
在这里我们定义Sni为n个a[i][0]项和 SSni为Sni的前n项和依此类推
未来了避免书写SSSSni的情况用mSni表示
例如3Sni就是SSSni; 这时候m=0就表示a[i][0]的值

我们通过手写能够知道a[n][m]的值为
(n-1)Smi+(n-2)Smi+…+(n-n)Smi;

而找这些值就很好处理了只要构造一个上三角矩阵就行了

初始化a[i][j] 使每行都为a[i][0] 在乘上上三角矩阵的k-1次幂就行了切记a*上三角不能反过来因为矩阵只有结合律没有交换律

这样a[0][i]都当成0的时候的a[n][m]值就求出来了

二、
计算a[i][0]都为0的时候a[n][m]的值计算出来

计算这个的时候就容易多了用我们要的结果就是计算数列的前n项和的前n项和的前n项和至于有多少层就看n的值 n是几就是几层

这个矩阵就明显复杂一点
10 0 10 10 10 10 10 10 10 10 10 10
1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 1

这是我构造出来的b矩阵
还有a矩阵是

233 3 233 233 233 233 233 233 233 233 233 233
下面的值不重要

a矩阵每项的值分别是
a[n] 3(a[n+1]-a[n]*10) 剩下的就是从1层前n项和到10层前n项和

上面解释过

最后n是几就选择第几层的前n项和

这样就把a[i][0]都为0的时候a[n][m]的值计算出来

最后两者相加就出现结果了

//因为分成两遍做得第二次初始化错误导致模拟赛后1分54秒才调好虽然1发ac了但是很不爽啊

附本题代码

-------------------------------------.

# include <iostream>
# include<stdio.h>
# include<algorithm>
# include<string.h>
using namespace std;

# define LL long long int

const int MOD = 1e7+7;
const int M = 12;

struct Matrix
{
    LL m[20][20];
} a,b;
int n,m;


Matrix operator * (Matrix a,Matrix b)
{
    Matrix c;
    for(int i=0; i<M; i++) //初始化矩阵
        for(int j=0; j<M; j++)
            c.m[i][j]= 0;

    for(int k=0; k<M; k++)
        for(int i=0; i<M; i++) //实现矩阵乘法
        {
            if(a.m[i][k] <= 0)  continue;
            for(int j=0; j<M; j++)
            {
                if(b.m[k][j] <= 0)    continue;
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    return c;
}

Matrix operator ^ (Matrix a,LL b)
{
    Matrix c;
    for(int i=0; i<M; i++) //初始化单位矩阵
        for(int j=0; j<M; j++)
            c.m[i][j]= ( i == j );

    while(b)
    {
        if(b&1) c= c * a ;
        b >>= 1;
        a = a * a ;
    }

    return c;
}


void init1()
{

    for(int i=0; i<M; i++)
    {
        for(int j=0; j<M; j++)
        {
            b.m[i][j]=0;
        }
    }

    for(int i=0; i<M; i++)
    {
        for(int j=i; j<M; j++)
        {
             b.m[i][j]=1;
        }
        b.m[0][i]=10;
    }

    b.m[0][1] = 0, b.m[1][0] = 1  ;

    return ;
}

void init2()
{
    for(int i=0; i<M; i++)
        for(int j=0; j<M; j++)
            b.m[i][j]=0;

    for(int i=0; i<M; i++)
        for(int j=i; j<M; j++)
             b.m[i][j]=1;

    return ;
}

int main()
{
    init1();

    while(~scanf("%d%d",&n,&m))
    {
        init1();

        for(int i=0;i<M;i++)
            a.m[0][i]=233;
        a.m[0][1]=3;

        b=b^(m-1);
        a=a*b;

        LL ans = a.m[0][n+1];

        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a.m[i][0]);
            for(int j=0; j<M; j++)
                a.m[i][j]=a.m[i][0]%MOD;
        }

        for(int i=0;i<M;i++)
            a.m[0][i]=0;


        init2();

        b=b^(m-1);
        a=a*b;

        for(int i=1;i<=n;i++)
            ans = (ans + a.m[i][n-i]) % MOD;

        printf("%I64d\n",ans);
    }
    return 0;
}