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

Tabris

CSDN数学思维

发布于：2016年7月29日

次浏览

[原创]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 了但是很不爽啊

附本题代码

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

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

# 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;
}

本页文档最后更新于：2021年5月16日

CSDN

矩阵快速幂

matrix