BuringStraw

Addition and Subtraction#

Very simple, just add the corresponding positions (Mr. Yu: This is not the focus for today!!!

Scalar Multiplication#

Well, just multiply all elements by that number

Matrix Multiplication#

More complicated,

A*B first requires the number of columns in A to be equal to the number of rows in B

Then take a look at the diagram, A goes horizontally, B goes vertically,

C[i][j]=A[i][k]*A[k][j] added up, 1<=k<=number of columns in A (or number of rows in B)

(Chinese characters represent the ith row of the result, numbers represent the jth column of the result.

Wrote a little code

#include<iostream>
using namespace std;

const int MAXN=1e4+5;

int a[MAXN][MAXN],b[MAXN][MAXN],c[MAXN][MAXN];

int main(){
	int h1,l1,h2,l2;
	cin>>h1>>l1>>h2>>l2;
	if(l1!=h2){
		cout<<"Can't calculate\n";
		return 0;
	}
	for(int i=1;i<=h1;++i){
		for(int j=1;j<=l1;++j){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=h2;++i){
		for(int j=1;j<=l2;++j){
			cin>>b[i][j];
		}
	}
	for(int i=1;i<=h1;++i){
		for(int j=1;j<=l2;++j){
			int s=0;
			for(int k=1;k<=l1;++k){
				s=s+a[i][k]*b[k][j];
			}
			c[i][j]=s;
		}
	}
	for(int i=1;i<=h1;++i){
		for(int j=1;j<=l2;++j){
			cout<<c[i][j]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}

Transposition#

Change rows into columns and columns into rows

Then there are some properties

Recurrence Relation#

Write the recurrence relation as a matrix with only one row.

For example, Fibonacci, f[i]=f[i-1]+f[i-2]

Write it as [f[i],f[i-1]

Then [f[i-1],f[i-2]] multiplied by a specific n*n (number of elements) matrix A can become [f[i],f[i-1]]

Here we can find that A is

1 1
1 0 

So the ith term is [1,0]*A^(i-1)

Fast Exponentiation#

The principle is similar to that of integers, the code is as follows (the * operator needs to be overloaded)

matrix pow(int k){
    matrix res=*this;
    matrix ret(h,l);
    ret.cleanForPow();
    while(k){
        if(k&1){
        	ret=ret*res;
    	}
    	res=res*res;
    	k>>=1;
    }
    return ret;
}