构造矩阵+矩阵连乘+fibonacci

我会带着你远行 2022-06-17 06:49 243阅读 0赞

hdu1021 链接：[点击打开链接][Link 1]

题目解析：ACMer都喜欢一题多解，这样会使自己的境界不一样！

方法一：找规律；小乔出嫁了—周期；循环节。对4求模余2即可

方法二：用矩阵连乘，构造二阶的矩阵来实现。

代码实现1：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    int main()
    {
        /*int a[100];
        a[0]=7;
        a[1]=11;
        for(int i=2;i<=30;i++)
        {
            a[i]=a[i-1]+a[i-2];
            cout<<a[i];
            if(a[i]%3==0)
            cout<<"yes   ";
            else
                cout<<"no   ";
        }*/
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            if(n%4==2)
            {
                cout<<"yes"<<endl;
            }
            else
            {
                cout<<"no"<<endl;
            }
        }
        return 0;
    }
    /*
    18yes   29no   47no   76no   123yes   199no   322no   521no   843yes   1364no
    2207no   3571no   5778yes   9349no   15127no   24476no   39603yes   64079no
    103682no   167761no   271443yes   439204no   710647no   1149851no   1860498yes
    3010349no   4870847no   7881196no   12752043yes
    */

代码实现2：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const int maxn=2;
    
    struct Matrix
    {
        int m[maxn][maxn];
    };
    
    Matrix I= {1,0,
               0,1
              };
    Matrix P= {1,1,
               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])%3;
                    ///c.m[i][j]+=a.m[i][k]*b.m[k][j];//因为数据比较小，这样也可以
                }
                c.m[i][j]%=3;
            }
        }
        return c;
    }
    
    Matrix quickpow(int 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()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0 || n==1)
            {
                cout<<"no"<<endl;
            }
            else
            {
                Matrix ans=quickpow(n-1);
                int sum=((ans.m[0][0]*11+ans.m[0][1]*7)%3+3)%3;
                if(sum%3==0)
                {
                    cout<<"yes"<<endl;
                }
                else
                {
                    cout<<"no"<<endl;
                }
            }
        }
        return 0;
    }

hdu3494 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=3493][http_acm.hdu.edu.cn_showproblem.php_pid_3493]

题目分析：此题需要根据题意先推导出递推公式，然后再采用构造矩阵的方法。

代码实现：

模板代码：

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    // m^n % k
    int quickpow(int m,int n,int k)
    {
        int b = 1;
        while (n > 0)
        {
            if (n & 1)
                b = (b*m)%k;
            n = n >> 1 ;
            m = (m*m)%k;
        }
        return b;
    }
    
    //HOJ 3493
    /*===================================*/
    /*
    || 快速幂（quickpow）模板
    || P 为等比，I 为单位矩阵
    || MAX 要初始化！！！！
    ||
    /*===================================*/
    /*****************************************************/
    
    const int MAX = 3;
    
    typedef  struct
    {
        int  m[MAX][MAX];
    }  Matrix;
    
    Matrix P = {5,-7,4,
                1,0,0,
                0,1,0,
               };
    
    Matrix I = {1,0,0,
                0,1,0,
                0,0,1,
               };
    
    Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
    {
        int i,j,k;
        Matrix c;
        for (i = 0 ; i < MAX; i++)
            for (j = 0; j < MAX; j++)
            {
                c.m[i][j] = 0;
                for (k = 0; k < MAX; k++)
                    c.m[i][j] += (a.m[i][k] * b.m[k][j])%9997;
                c.m[i][j] %= 9997;
            }
        return c;
    }
    
    Matrix quickpow(long long n)
    {
        Matrix m = P, b = I;
        while (n >= 1)
        {
            if (n & 1)
                b = matrixmul(b,m);
            n = n >> 1;
            m = matrixmul(m,m);
        }
        return b;
    }
    /*************************************/
    
    int main()
    {
        Matrix re;
        int f[3] = {2,6,19};
        long long n;
        while (scanf("%I64d",&n) && n != 0)
        {
            if (n == 1)
                printf("1\n");
            else if (n <= 4)
                printf("%d\n",f[n-2]);
            else
            {
                re = quickpow(n - 4);
                printf("%d\n",(((re.m[0][0]*f[2])
                                + (re.m[0][1]*f[1]) + (re.m[0][2]*f[0])) %9997 + 9997) % 9997);
            }
        }
        return 0;
    }

My ugly code but truth：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    const long long maxn=3;
    const long long mod=9997;
    
    struct mat
    {
        long long m[maxn][maxn];
    };
    
    mat P={5,-7,4,
            1,0,0,
            0,1,0};
    mat I={1,0,0,
            0,1,0,
            0,0,1};
    
    mat multiply(mat a,mat b)
    {
        mat c;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                c.m[i][j]=0;
                for(int k=0;k<3;k++)
                {
                    c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
                }
                c.m[i][j]=c.m[i][j]%mod;
            }
        }
        return c;
    }
    
    mat quickpow(long long n)
    {
        mat A=I;
        mat PP=P;
        while(n>0)
        {
            if(n&1)
                A=multiply(A,PP);
            n>>=1;
            PP=multiply(PP,PP);
        }
        return A;
    }
    
    int main()
    {
        long long n;
        long long sum;
        while(scanf("%I64d",&n)!=EOF)
        {
            if(n==0) break;
            else if(n==1) sum=1;
            else if(n==2) sum=2;
            else if(n==3) sum=6;
            else
            {
                mat ans=quickpow(n-4);
    
                sum=(((ans.m[0][0]*19)%mod+(ans.m[0][1]*6)%mod+(ans.m[0][2]*2)%mod)%mod+mod)%mod;
            }
            printf("%I64d\n",sum);
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1021
[http_acm.hdu.edu.cn_showproblem.php_pid_3493]: http://acm.hdu.edu.cn/showproblem.php?pid=3493