Reading comprehension HDU - 4990 （矩阵快速幂 or 快速幂+等比数列）

for(i=;i<=n;i++)

{

      if(i&)ans=(ans*+)%m;

      else ans=ans*%m;

}

给定n，m。让你用O(log(n))以下时间算出ans。

打表，推出 ans[i] = 2^(i-1) + f[i-2]

故　i奇数：ans[i] = 2^(i-1) + 2^(i-3) ... + 1;

　　i偶数：ans[i] = 2^(i-1) + 2^(i-3) ... + 2;

故可以用等比数列求和公式。

公式涉及除法。我也没弄懂为啥不能用逆元，貌似说是啥逆元可能不存在。

所以a/b % m == a%(b*m) / b 直接搞了。

#include <cstdio>

#include<iostream>

#include <cstring>

#include <cmath>

#include <algorithm>

#include<vector>

typedef long long LL;

LL quick_pow(LL a, LL b, LL m)

{

    LL ans = , base = a % m;

    while(b)

    {

        if (b & ) ans = (ans * base) % m;

        base = (base * base) % m;

        b >>= ;

    }

    return ans;

}

int main()

{

    LL n, m;

    while(~scanf("%lld%lld", &n, &m))

    {

        LL a1 = (n % ) ?  : ;

        LL sum = a1 * (quick_pow(, (n+)/, *m) - );

        LL ans = (sum % ( * m)) / ;

        printf("%lld\n", ans);

    }

}

第一次学矩阵快速幂，再贴个矩阵快速幂的板子。

f[n] = f[n-1] + 2 * f[n-2] + 1，故可以构造矩阵

f[n-] f[n-]                        f[n-]   f[n]

                             =

模板来源：https://blog.csdn.net/u012860063/article/details/39123605

#include <cstdio>

#include<iostream>

#include <cstring>

#include <cmath>

#include <algorithm>

#include<vector>

typedef long long LL;

struct Matrix

{

    LL m[][];

} I, A, B, T;

LL a,b,n, mod;

int ssize = ;

Matrix Mul(Matrix a,Matrix b)

{

    int i,j,k;

    Matrix c;

    for (i = ; i <= ssize; i++)

        for(j = ; j <= ssize; j++)

        {

            c.m[i][j]=;

            for(k = ; k <= ssize; k++)

            {

                c.m[i][j]+=(a.m[i][k]*b.m[k][j]);

                c.m[i][j]%=mod;

            }

        }

    return c;

}

Matrix quickpagow(int n)

{

    Matrix m = A, b = I;

    while(n)

    {

        if(n & ) b = Mul(b, m);

        n >>= ;

        m = Mul(m, m);

    }

    return b;

}

int main()

{

    while(~scanf("%lld%lld",&n, &mod))

    {

        memset(I.m,,sizeof(I.m));

        memset(A.m,,sizeof(A.m));

        memset(B.m,,sizeof(B.m));

        for(int i = ; i <= ssize; i++) I.m[i][i] = ;

        //I是单位矩阵

        B.m[][] = , B.m[][] = , B.m[][] = ;

        A.m[][] = ;

        A.m[][] = A.m[][] = A.m[][] = A.m[][] = ;

        if(n == ) printf("%lld\n", % mod);

        else if(n == ) printf("%lld\n", % mod);

        else

        {

            T = quickpagow(n-);

            T = Mul(B, T);

            printf("%lld\n",T.m[][] % mod);

        }

    }

}

巴特西

Reading comprehension HDU - 4990 （矩阵快速幂 or 快速幂+等比数列）

最新文章

热门文章