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.****.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);
        }
    }
}