一.矩陣與模板

【模板】矩陣求和

時間限制：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 longint 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;
}

?