矩阵加速!

P1939 【模板】矩阵加速（数列）

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
const long long mod = 1e9+7;
typedef long long ll;
struct Matrix
{
    ll a[5][5];
    Matrix()  //void Clear() 这样可以赋值！
    {
        memset(a,0,sizeof a);
    }
};
/*
Matrix base = {{
    {1,1,1},
    {1,1,0}
}};
*/
Matrix operator *(const Matrix &x,const Matrix &y)
{
    Matrix res;
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++) res.a[i][j] = 0;
    }
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            for(int k=1; k<=3; k++)
            {
                res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
            }
        }
    }
    return res;
}

int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        if(n <= 3) printf("1\n");
        else
        {
            int cnt = n - 3;
            Matrix res,base;
            for(int i=1; i<=3; i++) res.a[i][i] = 1;
            base.a[1][1] = base.a[1][2] = base.a[2][3] = base.a[3][1] = 1;
            while(cnt)
            {
                if(cnt & 1) res = res * base;
                base = base * base;
                cnt /= 2;
            }
            ll ans = (res.a[1][1] + res.a[2][1] + res.a[3][1])%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

P3390 【模板】矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll n,k;
struct Matrix
{
    ll a[109][109];
};
Matrix operator *(const Matrix &x,const Matrix &y)
{
    Matrix res;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) res.a[i][j] = 0;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<=n; k++)
            {
                res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
            }
        }
    }
    return res;
}

int main()
{
    Matrix x,res;
    cin >> n >> k;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) scanf("%d",&x.a[i][j]);
    }
    for(int i=1; i<=n; i++) res.a[i][i] = 1;
    while(k)
    {
        if(k & 1) res = res * x;
        x = x * x;
        k /= 2;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) printf("%d%s",res.a[i][j],j == n ? "\n" : " ");
    }
    return 0;
}