矩阵乘法
Matrix，支持二维 initializer_list 初始化。支持矩阵加法、矩阵乘法。重载 +、+=、*、*=。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct Matrix{
int n,m;
int a[3][3];
Matrix(int nn=-1,int mm=-1){
if(mm==-1){
mm=nn;
}
if(nn!=-1){
n=nn,m=mm;
}else{
n=0,m=0;
}
memset(a,0,sizeof(a));
}
Matrix(initializer_list<initializer_list<int>> x){
n=x.size();m=0;
for(auto &i:x){
m=max(m,(int)i.size());
}
int pi=0;
for(auto &i:x){
int pj=0;
for(auto &j:i){
a[pi][pj]=j;
pj++;
}
pi++;
}
}
int* operator [](const int &x){
return a[x];
}
void unit(){
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
a[i][i]=1;
}
}
void print(){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<a[i][j]<<' ';
}
cout<<endl;
}
}
};
Matrix operator *(Matrix A,Matrix B){
Matrix C(A.n,B.m);
for(int i=0;i<A.n;i++){
for(int j=0;j<B.m;j++){
for(int k=0;k<A.m;k++){
C[i][j]+=A[i][k]*B[k][j];
}
}
}
return C;
}
Matrix& operator *=(Matrix &A,Matrix B){
return A=A*B;
}
Matrix operator +(Matrix A,Matrix B){
Matrix C(A.n,A.m);
for(int i=0;i<A.n;i++){
for(int j=0;j<A.m;j++){
C[i][j]=A[i][j]+B[i][j];
}
}
return C;
}
Matrix& operator +=(Matrix &A,Matrix B){
for(int i=0;i<A.n;i++){
for(int j=0;j<A.m;j++){
A[i][j]+=B[i][j];
}
}
return A;
}
Barrett 约减
调用 Barrett.build(P) 更新模数为 P，调用 Barrett(x) 计算 x%P。
支持 $\left[-2^{63},2^{63}\right)$ 内的整数取模，模数范围为 $[2,2^{31})$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
typedef __int128 lll;
struct Barrett{
ll p,m;
inline void build(int P){
p=P;
m=((lll)1<<64)/p;
}
inline ll operator ()(ll x){
ll ans=x-((lll)x*m>>64)*p;
if(ans>=p){
ans-=p;
}
return ans;
}
}Barrett;
