牛马封装矩阵，包含各种牛马运算，具体看下面。 注： - 没有经过长期测试，存在的 **bz** 概率 - vector 存储常数较大，建议开 **O2** - 模数可以自己修改 - 模数在 int 范围内不用开 long long 即可使用，模数较大请自行改 long long - 如有用到需要求逆的运算，若 p 不为质数会报错，使用 Miller Rabin 判断质数 ```cpp const int p=1e9+7; struct matrix{ int n, m; vector<vector<int> > a; matrix(int _n=0, int _m=0) { n=_n, m=_m; if (!m) { m=n; a=vector<vector<int> >(n+1, vector<int> (m+1)); for (int i=1; i<=n; i++) a[i][i]=1; } else a=vector<vector<int> >(n+1, vector<int> (m+1)); } vector<int>& operator[](int x) & {return a[x];} const vector<int>& operator[](int x) const& {return a[x];} int Read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } void read() { // n=Read(), m=Read(); a=vector<vector<int> >(n+1, vector<int> (m+1)); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) a[i][j]=Read(); } void Write(int x) { if (x<0) { putchar('-'); x=-x; } if (x/10) Write(x/10); putchar(x%10+48); } void write() { // Write(n); putchar(' '); // Write(m); putchar('\n'); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) Write(a[i][j]), putchar(' '); putchar('\n'); } } matrix operator + (const matrix b) const { assert(n==b.n && m==b.m); matrix r(n, m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=(a[i][j]+b[i][j])%p; return r; } matrix operator - (const matrix b) const { assert(n==b.n && m==b.m); matrix r(n, m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=(a[i][j]-b[i][j]+p)%p; return r; } matrix operator * (const int k) const { matrix r(n, m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=1ll*a[i][j]*k%p; return r; } matrix operator * (const matrix b) const { assert(m==b.n); matrix r(n, b.m); for (int i=1; i<=n; i++) for (int k=1; k<=m; k++) for (int j=1; j<=b.m; j++) r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j])%p; return r; } matrix operator += (const matrix b) {return *this=*this+b;} matrix operator -= (const matrix b) {return *this=*this-b;} matrix operator *= (const int k) {return *this=*this*k;} matrix operator *= (const matrix b) {return *this=*this*b;} bool operator == (const matrix b) const { if (n!=b.n || m!=b.m) return 0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (a[i][j]!=b[i][j]) return 0; return 1; } bool operator != (const matrix b) const { return !(*this==b); } matrix operator ^ (int k) const { assert(n==m || k<=1); matrix r(m), a=*this; while (k) { if (k&1) r*=a; a*=a; k>>=1; } return r; } matrix operator ^= (int k) {return *this=*this^k;} int power(int x, int y, int p) { int r=1; while (y) { if (y&1) r=1ll*r*x%p; x=1ll*x*x%p; y>>=1; } return r; } bool is_prime(int n) { if (n<3 || n%2==0) return n==2; int a=n-1, b=0; while (a%2==0) a/=2, b++; for (int i=1, j; i<=10; i++) { int x=rand()%(n-2)+2, v=power(x, a, n); if (v==1) continue; for (j=0; j<b; j++) { if (v==n-1) break; v=1ll*v*v%n; } if (j>=b) return 0; } return 1; } int inv(int x) { assert(is_prime(p)); return power(x, p-2, p); } matrix inv() { matrix x=*this, y(n); for (int i=1; i<=n; i++) { int pos=i; for (int j=i+1; j<=n; j++) if (abs(x[j][i])>abs(x[pos][i])) pos=j; if (pos!=i) swap(x[i], x[pos]), swap(y[i], y[pos]); if (!x[i][i]) {matrix t(-1, -1); return t;} int tt=inv(x[i][i]); for (int j=1; j<=n; j++) { if (j==i) continue; int t=1ll*tt*x[j][i]%p; for (int k=1; k<=n; k++) { x[j][k]=((x[j][k]-1ll*t*x[i][k]%p)%p+p)%p; y[j][k]=((y[j][k]-1ll*t*y[i][k]%p)%p+p)%p; } } for (int j=1; j<=n; j++) { x[i][j]=1ll*x[i][j]*tt%p; y[i][j]=1ll*y[i][j]*tt%p; } } return y; } matrix operator / (const int k) { matrix r(n, m); int t=inv(k); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=1ll*a[i][j]*t%p; return r; } matrix operator / (matrix b) const { b=b.inv(); assert(m==b.n); matrix r(n, b.m); for (int i=1; i<=n; i++) for (int k=1; k<=m; k++) for (int j=1; j<=b.m; j++) r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j])%p; return r; } matrix operator /= (const int k) {return *this=*this/k;} matrix operator /= (const matrix b) {return *this=*this/b;} }; ``` ### 牛马用法 ##### 基本操作 生成一个空矩阵（$0\times 0$） ```cpp matrix a; ``` 生成一个单位矩阵（$n\times n$） ```cpp matrix a(n); ``` 生成一个 $n\times m$ 的矩阵 ```cpp matrix a(n,m); ``` 读入一个矩阵（$n$ 和 $m$ 已知） ```cpp matrix a(n,m); a.read(); //----------------------- matrix a; scanf("%d%d", &a.n, &a.m); a.read(); ``` 输出一个矩阵（不会输出长和宽） ```cpp a.write(); ``` ##### 牛马操作 直接访问一个矩阵的某一位 ```cpp matrix a(3); printf("%d\n", a[3][3]); ``` 判断两个矩阵是否相等 ```cpp if (a==b) printf("1"); if (a!=b) printf("0"); ``` ##### 基本运算 加、减、数乘、数除（不可加、减时会报错） ```cpp matrix a, b, c; int k; c=a+b; a+=b; //------------- c=a-b; a-=b; //------------- c=a*k; c*=k //------------- c=a/k; c/=k; ``` ##### 牛马运算 矩阵乘法（不可乘时会报错） ```cpp matrix a, b, c; c=a*b; //----------- a*=b; ``` 矩阵快速幂 ```cpp matrix a, b; int k; b=a^k; //--------- a^=k; ``` 矩阵求逆（无逆时返回 $n=-1,m=-1$） ```cpp matrix a, b; b=a.inv(); ``` 矩阵除法（无法除时会报错） ```cpp matrix a, b, c; c=a/b; //--------- a/=b; ``` Loading... 牛马封装矩阵，包含各种牛马运算，具体看下面。 注： - 没有经过长期测试，存在的 **bz** 概率 - vector 存储常数较大，建议开 **O2** - 模数可以自己修改 - 模数在 int 范围内不用开 long long 即可使用，模数较大请自行改 long long - 如有用到需要求逆的运算，若 p 不为质数会报错，使用 Miller Rabin 判断质数 ```cpp const int p=1e9+7; struct matrix{ int n, m; vector<vector<int> > a; matrix(int _n=0, int _m=0) { n=_n, m=_m; if (!m) { m=n; a=vector<vector<int> >(n+1, vector<int> (m+1)); for (int i=1; i<=n; i++) a[i][i]=1; } else a=vector<vector<int> >(n+1, vector<int> (m+1)); } vector<int>& operator[](int x) & {return a[x];} const vector<int>& operator[](int x) const& {return a[x];} int Read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } void read() { // n=Read(), m=Read(); a=vector<vector<int> >(n+1, vector<int> (m+1)); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) a[i][j]=Read(); } void Write(int x) { if (x<0) { putchar('-'); x=-x; } if (x/10) Write(x/10); putchar(x%10+48); } void write() { // Write(n); putchar(' '); // Write(m); putchar('\n'); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) Write(a[i][j]), putchar(' '); putchar('\n'); } } matrix operator + (const matrix b) const { assert(n==b.n && m==b.m); matrix r(n, m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=(a[i][j]+b[i][j])%p; return r; } matrix operator - (const matrix b) const { assert(n==b.n && m==b.m); matrix r(n, m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=(a[i][j]-b[i][j]+p)%p; return r; } matrix operator * (const int k) const { matrix r(n, m); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=1ll*a[i][j]*k%p; return r; } matrix operator * (const matrix b) const { assert(m==b.n); matrix r(n, b.m); for (int i=1; i<=n; i++) for (int k=1; k<=m; k++) for (int j=1; j<=b.m; j++) r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j])%p; return r; } matrix operator += (const matrix b) {return *this=*this+b;} matrix operator -= (const matrix b) {return *this=*this-b;} matrix operator *= (const int k) {return *this=*this*k;} matrix operator *= (const matrix b) {return *this=*this*b;} bool operator == (const matrix b) const { if (n!=b.n || m!=b.m) return 0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (a[i][j]!=b[i][j]) return 0; return 1; } bool operator != (const matrix b) const { return !(*this==b); } matrix operator ^ (int k) const { assert(n==m || k<=1); matrix r(m), a=*this; while (k) { if (k&1) r*=a; a*=a; k>>=1; } return r; } matrix operator ^= (int k) {return *this=*this^k;} int power(int x, int y, int p) { int r=1; while (y) { if (y&1) r=1ll*r*x%p; x=1ll*x*x%p; y>>=1; } return r; } bool is_prime(int n) { if (n<3 || n%2==0) return n==2; int a=n-1, b=0; while (a%2==0) a/=2, b++; for (int i=1, j; i<=10; i++) { int x=rand()%(n-2)+2, v=power(x, a, n); if (v==1) continue; for (j=0; j<b; j++) { if (v==n-1) break; v=1ll*v*v%n; } if (j>=b) return 0; } return 1; } int inv(int x) { assert(is_prime(p)); return power(x, p-2, p); } matrix inv() { matrix x=*this, y(n); for (int i=1; i<=n; i++) { int pos=i; for (int j=i+1; j<=n; j++) if (abs(x[j][i])>abs(x[pos][i])) pos=j; if (pos!=i) swap(x[i], x[pos]), swap(y[i], y[pos]); if (!x[i][i]) {matrix t(-1, -1); return t;} int tt=inv(x[i][i]); for (int j=1; j<=n; j++) { if (j==i) continue; int t=1ll*tt*x[j][i]%p; for (int k=1; k<=n; k++) { x[j][k]=((x[j][k]-1ll*t*x[i][k]%p)%p+p)%p; y[j][k]=((y[j][k]-1ll*t*y[i][k]%p)%p+p)%p; } } for (int j=1; j<=n; j++) { x[i][j]=1ll*x[i][j]*tt%p; y[i][j]=1ll*y[i][j]*tt%p; } } return y; } matrix operator / (const int k) { matrix r(n, m); int t=inv(k); for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) r[i][j]=1ll*a[i][j]*t%p; return r; } matrix operator / (matrix b) const { b=b.inv(); assert(m==b.n); matrix r(n, b.m); for (int i=1; i<=n; i++) for (int k=1; k<=m; k++) for (int j=1; j<=b.m; j++) r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j])%p; return r; } matrix operator /= (const int k) {return *this=*this/k;} matrix operator /= (const matrix b) {return *this=*this/b;} }; ``` ### 牛马用法 ##### 基本操作 生成一个空矩阵（$0\times 0$） ```cpp matrix a; ``` 生成一个单位矩阵（$n\times n$） ```cpp matrix a(n); ``` 生成一个 $n\times m$ 的矩阵 ```cpp matrix a(n,m); ``` 读入一个矩阵（$n$ 和 $m$ 已知） ```cpp matrix a(n,m); a.read(); //----------------------- matrix a; scanf("%d%d", &a.n, &a.m); a.read(); ``` 输出一个矩阵（不会输出长和宽） ```cpp a.write(); ``` ##### 牛马操作 直接访问一个矩阵的某一位 ```cpp matrix a(3); printf("%d\n", a[3][3]); ``` 判断两个矩阵是否相等 ```cpp if (a==b) printf("1"); if (a!=b) printf("0"); ``` ##### 基本运算 加、减、数乘、数除（不可加、减时会报错） ```cpp matrix a, b, c; int k; c=a+b; a+=b; //------------- c=a-b; a-=b; //------------- c=a*k; c*=k //------------- c=a/k; c/=k; ``` ##### 牛马运算 矩阵乘法（不可乘时会报错） ```cpp matrix a, b, c; c=a*b; //----------- a*=b; ``` 矩阵快速幂 ```cpp matrix a, b; int k; b=a^k; //--------- a^=k; ``` 矩阵求逆（无逆时返回 $n=-1,m=-1$） ```cpp matrix a, b; b=a.inv(); ``` 矩阵除法（无法除时会报错） ```cpp matrix a, b, c; c=a/b; //--------- a/=b; ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏