目录
二、线性代数
矩阵模板
namespace Matrix{
struct matrix{
int hang, lie;
vector <vector<int >> num;
matrix(int x = 0, int y = 0){
hang = x;
lie = y;
num.resize(x + 1);
for(int i = 1; i <= x; i ++)
num[i].resize(y + 1);
}
void out(){
for(int i = 1; i <= hang; i ++){
for(int j = 1; j <= lie; j ++)
cout << num[i][j] << " ";
cout << endl;
}
}
}no;
matrix E(int n){
matrix ret(n, n);
for(int i = 1; i <= n; i ++)
ret.num[i][i] = 1;
return ret;
}
matrix operator * (matrix a, matrix b){
matrix ret(a.hang, b.lie);
for(int i = 1; i <= ret.hang; i ++)
for(int j = 1; j <= ret.lie; j ++)
for(int k = 1; k <= a.lie; k ++)
ret.num[i][j] = (ret.num[i][j] + 1ll * a.num[i][k] * b.num[k][j]) % mod;
return ret;
}
matrix operator * (int k, matrix b){
matrix ret = b;
for(int i = 1; i <= b.hang; i ++)
for(int j = 1; j <= b.lie; j ++)
ret.num[i][j] = 1ll * k * b.num[i][j] % mod;
return ret;
}
matrix operator + (matrix a, matrix b){
matrix ret = a;
for(int i = 1; i <= a.hang; i ++)
for(int j = 1; j <= a.lie; j ++){
ret.num[i][j] = a.num[i][j] + b.num[i][j];
if(ret.num[i][j] >= mod) ret.num[i][j] -= mod;
}
return ret;
}
matrix quickpow(matrix x, int b){
if(b == 0) return E(x.lie);
if(b == 1) return x;
matrix l = quickpow(x, b >> 1);
l = l * l;
if(b & 1)
l = l * x;
return l;
}
}