矩阵及矩阵快速幂

一.矩阵与模板

【模板】矩阵求和

时间限制：1秒        内存限制：128M

题目描述

给出两个𝑛行𝑚列的矩阵，求两个矩阵的和

输入描述

第一行输入两个以空格分隔的整数𝑛,𝑚，表示矩阵的行数和列数

接下来的𝑛行，每行𝑚个以空格分隔的实数𝑇1[𝑖][𝑗]，表示第一个矩阵

接下来的𝑛行，每行m个以空格分隔的实数𝑇2[𝑖][𝑗]，表示第二个矩阵

1≤𝑛≤100,1≤𝑚≤100

0≤𝑇1[𝑖][𝑗]≤1000,0≤𝑇2[𝑖][𝑗]≤1000

cout << fixed << setprecision(2) << x; 或者 printf(“%.2lf”,x); 可以用来输出小数x并保留两位小数

输出描述

输出n行，每行包含𝑚个以空格分隔的实数，表示两个矩阵相加的结果

矩阵中的实数都保留2位小数

样例输入

1. 2 3
2. 1.1 1.2 1.3
3. 2.1 2.2 2.3
4. 1.1 1.2 1.3
5. 2.1 2.2 2.3

样例输出

1. 2.20 2.40 2.60
2. 4.20 4.40 4.60

#include<iostream>
using namespace std;
double a[105][105],o;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>o;
            a[i][j]+=o;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>o;
            a[i][j]+=o;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%.2lf ",a[i][j]);
        cout<<"\n";
    }
    return 0;
}

【模板】矩阵乘法

时间限制：1秒        内存限制：128M

题目描述

给定两个矩阵𝑎,𝑏求矩阵𝑐=𝑎∗𝑏

输入描述

第一行四个整数𝑚1,𝑛1,𝑚2,𝑛2，代表第一个矩阵和第二个矩阵的列数和行数。

接下来𝑛1行，每行m1个整数，代表第一个矩阵。

之后𝑛2行，每行m2个整数，代表第二个矩阵。

数据保证𝑚1=𝑛2。所有的输入数据不超过100

输出描述

输出𝑛1行，每行𝑚2个整数，代表矩阵𝑐。

样例输入1

1. 2 2 2 2
2. 2 2
3. 2 2
4. 2 2
5. 2 2

样例输出1

1. 8 8
2. 8 8

样例输入2

1. 2 2 2 2
2. 1 2
3. 3 1
4. 2 5
5. 1 7

样例输出2

1. 4 19
2. 7 22

#include<iostream>
using namespace std;
const int N = 105;
int n1,n2,m1,m2;
int a[N][N],b[N][N],c[N][N];
int main(){
    cin>>m1>>n1>>m2>>n2;
    for(int i=1;i<=n1;i++)
        for(int j=1;j<=m1;j++)
            cin>>a[i][j];
    for(int i=1;i<=n2;i++)
        for(int j=1;j<=m2;j++)
            cin>>b[i][j];
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=m2;j++){
            for(int k=1;k<=m1;k++){
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=m2;j++){
            cout<<c[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

 【模板】矩阵加速

时间限制：1秒        内存限制：128M

题目描述

已知一个数列a，满足：

求𝑎数列的第𝑛项模10^9+7的值。

输入描述

第一行一个整数𝑇(1≤𝑇≤100)，表示询问的次数。

以下𝑇个正整数𝑛(1≤𝑛≤2×10^9)。

输出描述

每行输出一个非负整数表示答案。

样例输入

1. 3
2. 6
3. 8
4. 10

样例输出

1. 4
2. 9
3. 19

#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const int N = 2;
const int mod = 1e9+7;
ll a[N][N]={{1,1},{1,0}};
ll s[N][N]={{1,1},{0,0}};
ll n,T;
struct Mat//封装好的矩阵操作
{
    #define int long long
    int a[105][105];
    int r, c;
    Mat(int _r = 0, int _c = 0)
    {
        r = _r, c = _c;
        memset(a, 0, sizeof(a));
        if (c == 0)
            c = r; //这样传入一个参数可以构造方阵
    }
    void unit()
    { //将自身变成单位矩阵
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= r; i++)
            a[i][i] = 1;
    }
    friend Mat operator+(Mat x, Mat y)
    {
        Mat ans(x.r, x.c);
        for (int i = 1; i <= x.r; i++)
            for (int j = 1; j <= x.c; j++)
                ans.a[i][j] = x.a[i][j] + y.a[i][j];
        return ans;
    }
    friend Mat operator-(Mat x, Mat y)
    {
        Mat ans(x.r, x.c);
        for (int i = 1; i <= x.r; i++)
            for (int j = 1; j <= x.c; j++)
                ans.a[i][j] = x.a[i][j] - y.a[i][j];
        return ans;
    }
    friend Mat operator*(Mat x, Mat y)
    {
        Mat ans(x.r, y.c);
        for (int i = 1; i <= x.r; i++)
            for (int j = 1; j <= y.c; j++)
                for (int k = 1; k <= x.c; k++)
                    ans.a[i][j] += x.a[i][k] * y.a[k][j];
        return ans;
    }
    friend Mat operator%(Mat x, int t)
    {
        for (int i = 1; i <= x.r; i++)
            for (int j = 1; j <= x.c; j++)
                x.a[i][j] %= t;
        return x;
    }
    void out()
    {
        for (int i = 1; i <= r; i++)
        {
            for (int j = 1; j <= c; j++)
                cout << a[i][j] << ' ';
            cout << endl;
        }
    }
    Mat pow(ll b)
    {
        Mat ans(r, c), a = *this;
        ans.unit();
        while (b)
        {
            if (b & 1)
                ans = ans * a;
            a = a * a;
            b >>= 1;
        }
        return ans;
    }
    Mat pow(ll b, ll p)
    {
        Mat ans(r, c), a = *this;
        ans.unit();
        while (b)
        {
            if (b & 1)
                ans = ans * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return ans;
    }
    #undef int
};
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        if(n<=3){
            cout<<"1\n";
            continue;
        }
        Mat a(3),b(3);
        a.a[1][1]=1,a.a[1][2]=1,a.a[1][3]=1;
        b.a[1][1]=b.a[1][2]=b.a[2][3]=b.a[3][1]=1;
        a=a*b.pow(n-3,mod)%mod;
        cout<<a.a[1][1]<<"\n";
    }
    return 0;
}