构造矩阵解决问题【nyoj299 Matrix Power Series】

曾经终败给现在 2022-08-12 20:28 91阅读 0赞

矩阵的又一个新用法，构造矩阵进行快速幂。

比如拿 [ nyoj299 Matrix Power Series][nyoj299 Matrix Power Series] 来说

给出这样一个递推式：S = A \+ A2 \+ A3 \+ … + Ak.

让你求s，A是一个矩阵，而k非常大。怎么办呢？

推理发现：Fn = A + A\*F（n-1）

然后我们可以构造矩阵：

（Fn ，1 ） = （Fn-1 ，1） \* （A，0。A，1） = （F1 , 1） \* （A，0。A，1）^K-1

那么我们就可以用一个矩阵快速幂了。

下面是模板题目的代码：

#include <cstdio>
    #include <string>
    #include <cmath>
    #include <iostream>
    using namespace std;
    int M;
    const long long N = 32*2;
    long long t,b,c,f1,f2;
    struct tree  //基础矩阵
    {
        long long line,cal;
        long long a[N+1][N+1];
    };
    struct Node  //构造矩阵
    {
        long long line,cal;
        long long a[N+1][N+1];
        Node(tree x)
        {
            line=x.line*2;
            cal=2*x.cal;
            for(int i=0;i<x.line*2;i++)
            {
                for(int j=0;j<x.cal;j++)
                {
                    a[i][j]=x.a[i%x.line][j];
                }
            }
            for(int i=0;i<x.line;i++)
                for(int j=x.cal;j<x.cal*2;j++)
                    a[i][j]=0;
            for(int i=x.line;i<2*x.line;i++){
                for(int j=x.cal;j<2*x.cal;j++){
                    if(i==j)
                        a[i][j]=1;
                    else
                        a[i][j]=0;
                }
            }
        }
    };
    
    Node isit(Node x,long long c)  //矩阵初始化
    {
        for(long long i=0;i<N;i++)
            for(long long j=0;j<N;j++)
                x.a[i][j]=c;
        return x;
    }
    
    Node Matlab(Node x,Node s)  //矩阵乘法
    {
        Node ans(x);
        ans.line = x.line,ans.cal = s.cal;
        ans=isit(ans,0);
        for(long long i=0;i<x.line;i++)
        {
            for(long long j=0;j<x.cal;j++)
            {
                for(long long k=0;k<s.cal;k++)
                {
                    ans.a[i][j] += x.a[i][k]*s.a[k][j];
                    ans.a[i][j]=(ans.a[i][j])%M;
                }
            }
        }
        return ans;
    }
    Node Fast_Matrax(tree x,long long n)  //矩阵快速幂
    {
        Node ans(x),tmp(x);
        for(int i=0;i<ans.line/2;i++)  //chushihua
        {
            for(int j=0;j<ans.cal;j++)
            {
                ans.a[i][j]=ans.a[i+ans.line/2][j];
                //printf("%d ",ans.a[i][j]);
            }
        }
        ans.line/=2;
        while(n>0)
        {
            if(n%2)
            {
                ans=Matlab(ans,tmp);
            }
            tmp=Matlab(tmp,tmp);
            n/=2;
        }
        return ans;
    }
    int main()
    {
        int n,k,m;
        while(~scanf("%d%d%d",&n,&k,&m))
        {
            M=m;
            tree p;
            p.line=n,p.cal=n;
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    scanf("%d",&p.a[i][j]);
            Node ans=Fast_Matrax(p,k-1);
            for(int i=0;i<ans.line;i++)
            {
                for(int j=0;j<ans.cal/2;j++)
                    printf("%d ",ans.a[i][j]);
                puts("");
            }
        }
        return 0;
    }

[nyoj299 Matrix Power Series]: http://acm.nyist.net/JudgeOnline/problem.php?pid=299