欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

矩阵快速幂-233 Matrix HDU - 5015

程序员文章站 2022-07-03 18:25:10
...

矩阵快速幂-233 Matrix HDU - 5015

题目:
wbx定义了一种新的矩阵,它的第一行是这样一些数:(a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333…) 除此之外,在这个矩阵里, 我们有 a i,j = a i-1,j +a i,j-1( i,j ≠ 0).现在给你 a 1,0,a 2,0,…,a n,0, 你能告诉wbx,a n,m 是多少吗?
Input
多组数据。

每一组数据第一行有两个正整数 n,m(n ≤ 10,m ≤ 10 9). 第二行是n个整数a 1,0,a 2,0,…,a n,0(0 ≤ a i,0 < 2 31).

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

题意:
给出矩阵第0行,第1~n列的初始值(分别是233,2333,23333,…)
给出递推公式:a(i,j)=a(i-1,j)+a(i,j-1)
现输入矩阵行数n,列数m,以及第1列,第1~n行的初始值,求出a(n,m)的值

题解:
矩阵快速幂-233 Matrix HDU - 5015
首先构造出关系矩阵
根据已给出的初始值容易看出,后一列第0行的值是前一列第0行的值的10倍+3,那么可得a(0,0)=23,构造a(0,n+1)=3最后加上。
于是初始矩阵第一列的值如下:
矩阵快速幂-233 Matrix HDU - 5015
可以确定第一列的值为10的n+1行的矩阵,因此该关系矩阵最后一列的值应该为1。
再根据递推式可得关系矩阵。
关系矩阵如图:
矩阵快速幂-233 Matrix HDU - 5015
那么求出关系矩阵Gm再乘初始矩阵的第一列即可。

代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=1e7+7 , N=15;
int n,m;
ll rec[N];//初始序列
ll ans=0;
void mat_mul(ll a[N][N],ll b[N][N])
{
    ll c[N][N];
    memset(c,0,sizeof(c));
    for(int k=0;k<=n+1;k++)
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
                c[i][j]=((c[i][j]+a[i][k]*b[k][j])%mod+mod)%mod;
    memcpy(a,c,sizeof(c));
}

void mat_pow(int k)
{
    ll M[N][N];//关系矩阵M
    memset(M,0,sizeof(M));//不可少!!!
    for(int i=0;i<=n;i++)//初始化
    {
        M[i][0]=10;
        M[i][n+1]=1;
        for(int j=1;j<i+1;j++)
            M[i][j]=1;
    }
    //将n+1列变成1
    M[n+1][n+1]=1;

    //矩阵快速幂
    ll E[N][N];//单位矩阵
    memset(E,0,sizeof(E));
    for(int i=0;i<=n+1;i++) E[i][i]=1;
    while(k)
    {
        if(k&1) mat_mul(E,M);
        mat_mul(M,M);
        k>>=1;
    }

    //最后将k次方关系矩阵E与初始序列rec相乘
    for(int i=0;i<=n+1;i++)
        ans=(ans+E[n][i]*rec[i])%mod;

}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        ans=0;
        rec[0]=23;
        rec[n+1]=3;
        for(int i=1;i<=n;i++)
            scanf("%d",&rec[i]);
        mat_pow(m);
        printf("%d\n",ans);
    }
    return 0;
}

总结:
数组开局部变量要注意初始化