AcWing 226. 233矩阵（矩阵快速幂+线性递推）打卡

题目：https://www.acwing.com/problem/content/228/

题意：有一个二维矩阵，这里只给你第一行和第一列，要你求出f[n][m],关系式有 1, f[0][m]=f[0][m-1]*10+3 2, f[n][m]=f[n-1][m]+f[n][m-1]

思路：我们可以看出这里n的范围很小 ,m的范围很大，我们直接递推过去肯定超时，线性递推超时，那么肯定要用矩阵快速幂，但是这个有事二维的

那么我们只能想下怎么改成是一维的递推式，我们可以发现n是特别小的，我们可以利用n范围小，直接存下一列都没有事

那么我们可以利用递推式简化成一下形式

AcWing 226. 233矩阵（矩阵快速幂+线性递推）打卡

这样我们就可以构造出一个关系n+2的矩阵

#include<bits/stdc++.h>
#define mod 10000007
using namespace std;
#define MAXN 35
typedef long long ll;
struct mat
{
    ll m[MAXN][MAXN];//矩阵结构体
}unit,g;//unit为单位矩阵，即主对角线全部为1，这样任何矩阵与单位矩阵相乘都为它本身

ll n,m;
mat msub(mat a,mat b)//矩阵相乘函数
{
    mat ret;
    ll x;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            x=0;
            for(int k=0;k<=n;k++)
            {
                x+=((a.m[i][k]*b.m[k][j])%mod);//取余
            }
            ret.m[i][j]=x%mod;//取余
        }
    }
    return ret;
}
void init_unit(){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            unit.m[i][j]=0;
            g.m[i][j]=0;
        }
    }
    for(int i=n-2;i>=0;i--){
        scanf("%lld",&unit.m[i][0]);
    }
    unit.m[n-1][0]=23;
    unit.m[n][0]=3; 
    for(int j=n;j>=0;j--){
        for(int i=0;i<=j;i++){
            if(j==n-1){
                g.m[i][j]=10;
            }
            else g.m[i][j]=1;
        }
    }
}
mat qpow(mat a,ll x)//快速幂
{
    mat ans=unit;
    while(x)
    {
        if(x&1) ans=msub(a,ans);
        a=msub(a,a);
        x>>=1;
    }
    return ans;
}

int main()
{
    ll x;
    while(scanf("%lld%lld",&n,&m)!=EOF){
        n++;
        init_unit();
        mat x=qpow(g,m);
        printf("%lld
",(x.m[0][0])%mod); 
    }
    return 0;
}

AcWing 226. 233矩阵 （矩阵快速幂+线性递推）打卡

相关推荐

AcWing 226. 233矩阵（矩阵快速幂+线性递推）打卡