fibonacci扩展+矩阵连乘

秒速五厘米 2022-06-17 09:37 164阅读 0赞

dhu1757 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1757][http_acm.hdu.edu.cn_showproblem.php_pid_1757]

题目分析：标准的构造矩阵矩阵连乘问题

代码实现：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const long long maxn=10;
    long long mod;
    long long data[maxn];
    long long f[maxn];
    struct Matrix
    {
        long long m[maxn][maxn];
    };
    
    Matrix I= { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 1
              };
    Matrix P= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
               1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
               0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
               0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
               0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
               0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
               0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
               0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
               0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
               0, 0, 0, 0, 0, 0, 0, 0, 1, 0
              };
    
    Matrix multiply(Matrix a,Matrix b)
    {
        Matrix c;
        for(int i=0; i<maxn; i++)
        {
            for(int j=0; j<maxn; j++)
            {
                c.m[i][j]=0;
                for(int k=0; k<maxn; k++)
                {
                    c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
                    ///c.m[i][j]+=a.m[i][k]*b.m[k][j];//因为数据比较小，这样也可以
                }
                c.m[i][j]%=mod;
            }
        }
        return c;
    }
    
    Matrix quickpow(long long n)
    {
        Matrix A=I;
        Matrix PP=P;
        while(n>=1)
        {
            if(n&1)
                A=multiply(A,PP);
            n>>=1;
            PP=multiply(PP,PP);
        }
        return A;
    }
    
    int main()
    {
        long long n;
        while(scanf("%I64d%I64d",&n,&mod)!=EOF)
        {
            for(int i=0; i<10; i++)
            {
                scanf("%I64d",&data[i]);
            }
            for(int i=0;i<maxn;i++)
            {
                P.m[0][i]=data[i];
            }
            for(int i=0;i<maxn;i++)
            {
                f[i]=i;
            }
            if(n<10)
            {
                cout<<data[n]<<endl;
            }
            else
            {
                Matrix ans=quickpow(n-9);
                long long sum=0;
                for(int i=0; i<10; i++)
                {
                    sum+=(ans.m[0][i]*f[9-i])%mod;
                    //cout<<sum<<"  llalalla"<<endl;
                }
                sum=(sum%mod+mod)%mod;
                cout<<sum<<endl;
            }
        }
        return 0;
    }

poj3070：题目链接：[http://poj.org/problem?id=3070][http_poj.org_problem_id_3070]

题目分析：构造矩阵，矩阵连乘

code：

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    const long long maxn=2;
    const long long mod=10000;
    struct Matrix
    {
        long long m[maxn][maxn];
    };
    
    Matrix I={  1,0,
                0,1};
    Matrix P={  1,1,
                1,0};
    
    Matrix mul(Matrix a,Matrix b)
    {
        Matrix c;
        for(int i=0;i<maxn;i++)
        {
            for(int j=0;j<maxn;j++)
            {
                c.m[i][j]=0;
                for(int k=0;k<maxn;k++)
                {
                    c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
                }
                c.m[i][j]%=mod;
            }
        }
        return c;
    }
    
    Matrix quickpow(long long n)
    {
        Matrix A=I;
        Matrix PP=P;
        while(n>=1)
        {
            if(n&1)
            {
                A=mul(A,PP);
            }
            n>>=1;
            PP=mul(PP,PP);
        }
        return A;
    }
    
    int main()
    {
        long long n;
        long long sum;
        while(scanf("%lld",&n)!=EOF)
        {
            if(n==-1)
                break;
            else
            {
                if(n<2)
                {
                    sum=n;
                }
                else
                {
                    Matrix ans=quickpow(n-1);
                    /*for(int i=0;i<maxn;i++)
                    {
                        for(int j=0;j<maxn;j++)
                        {
                            cout<<ans.m[i][j]<<"  ";
                        }
                        cout<<endl;
                    }*/
                    sum=((ans.m[0][0])%mod+mod)%mod;
                }
                cout<<sum<<endl;
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1757]: http://acm.hdu.edu.cn/showproblem.php?pid=1757
[http_poj.org_problem_id_3070]: http://poj.org/problem?id=3070