P1349题解

· · 题解

2325131433448687~

最近重温了矩阵乘法，A了这道题后看了看题解，没有特别详细的，我就来补一发。。。

Case 1

假设现在将问题简化为求斐波那契数列第n项Mod m的结果，且n<=10^6。。。

想必这个问题大家都会，只需要a[1]=1，a[2]=1，然后跑一边for循环，结束。。。

Case 2

现在，在Case 1的基础上，n改为n<=10^12，那么现在该如何解决呢？

此时，就需要用“矩阵快速幂”QWQ！

2.1 矩阵乘法

        矩阵乘法的定义如下：

        对于一个a * b的矩阵A，b * c的矩阵B，C=A * B

        那么Cij=Ai1 * B1j + Ai2 * B2j+ Ai3 * B3j + …… + Aib * Bbj（C的大小为a * c）

2.2 矩阵快速幂

        矩阵快速幂与快速幂相似，使用了位运算，将原本要进行的n次乘法变成了log n次，它的总时间复杂度为O（abclog n）。。。

        下面是最经典的矩阵快速幂的核心代码（P3390）：
        struct matrix
        {
            long long M[MAXN][MAXN];
            matrix operator *(const matrix B) const
            {
            matrix C;
            memset(C.M, 0, sizeof(C.M));
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    for(int k = 1; k <= n; k++)
                        C.M[i][j] = (C.M[i][j]+ M[i][k]*B.M[k][j]) % MOD;
                return C;
            }
        }A, res;

2.3 斐波那契数列取模与矩阵快速幂

        不难发现，

        f（n）     1 1   f（n-1）
        f（n-1）=  1 0 * f（n-2）

        于是，代码也就敲出来了，在这里就不展示了。。。

Case 3

那么对于本题，怎么做呢？

由于该题只是把斐波那契数列中的系数改了，所以公式应该也长得差不多。。。

只需试一试，公式就出来了：

f(n)     p 1    f(n-1)
f(n-1) = q 0 * f(n-2)

于是代码写出来了：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,m;
struct Matrix
{
    ll a[2][2]; 
    Matrix operator *(const Matrix B) const
    {
        Matrix C;
        memset(C.a,0,sizeof(C.a));
        for(ll i=0;i<2;++i)
        {
            for(ll j=0;j<2;++j)
            {
                for(ll k=0;k<2;++k)
                {
                    C.a[i][j]+=a[i][k]*B.a[k][j];
                    C.a[i][j]%=m;
                }
            }
        }
        return C;
    }
}res,A;
ll p,q,a1,a2;
Matrix Mul(Matrix a,ll b)
{
    Matrix ans=a;
    a.a[0][0]=p;
    a.a[0][1]=1;
    a.a[1][0]=q;
    while(b)
    {
        if(b&1)
            ans=ans*a;
        a=a*a;
        b=b>>1;
    }
    return ans;
}

int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&a1,&a2,&n,&m);
    A.a[0][0]=a2;
    A.a[0][1]=a1;
    Matrix res=Mul(A,n-2);
    printf("%lld",res.a[0][0]%m);
    return 0;
}

2325131433448687~