【BZOJ】4128: Matrix

题解

学习一下矩阵求逆

就是我们考虑这个矩阵
\(AA^{-1} = I\)
我们相当于让\(A\)乘上一个矩阵，变成\(I\)
我们可以利用初等行变换（只能应用初等行变换，或只应用初等列变换）

分三种
1.矩阵的两行互换
2.矩阵的一行加上k倍的另一行
3.矩阵的一行都乘上某个数

其实行变换的本质也可以写成一个矩阵！

我们把\(A\)消成1的过程中，对\(I\)进行同样的操作，就可以得到\(A^{-1}\)了

然后用map代替哈希记录一下就行

似乎这题不用求逆也行。。。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar(‘\n‘)
#define space putchar(‘ ‘)
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < ‘0‘ || c > ‘9‘) {
    if(c == ‘-‘) f = -1;
    c = getchar();
    }
    while(c >= ‘0‘ && c <= ‘9‘) {
    res = res * 10 + c - ‘0‘;
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar(‘-‘);}
    if(x >= 10) {
    out(x / 10);
    }
    putchar(‘0‘ + x % 10);
}
int MOD,N;
int inv[20005];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return a * b % MOD;
}
struct Matrix {
    int f[72][72];
    Matrix() {memset(f,0,sizeof(f));}
    friend Matrix operator * (const Matrix &a,const Matrix &b) {
    Matrix c;
    for(int i = 1 ; i <= N ; ++i) {
        for(int j = 1 ; j <= N ; ++j) {
        for(int k = 1 ; k <= N ; ++k) {
            c.f[i][j] = inc(c.f[i][j],mul(a.f[i][k],b.f[k][j]));
        }
        }
    }
    return c;
    }
    void unit() {
    for(int i = 1 ; i <= N ; ++i) f[i][i] = 1;
    }
    friend Matrix operator ~(Matrix a) {
    Matrix b;
    b.unit();
    for(int i = 1 ; i <= N ; ++i) {
        int l;
        for(l = i ; l <= N ; ++l) {
        if(a.f[l][i]) break;
        }
        if(l != i) {
        for(int j = 1 ; j <= N ; ++j) {
            swap(a.f[l][j],a.f[i][j]);
            swap(b.f[l][j],b.f[i][j]);
        }
        }
        int t = inv[a.f[i][i]];
        if(t) {
        for(int j = 1 ; j <= N ; ++j) {
        
            a.f[i][j] = mul(a.f[i][j],t);
            b.f[i][j] = mul(b.f[i][j],t);
        }
        }
        for(int j = 1 ; j <= N ; ++j) {
        if(j == i) continue;
        int t = a.f[j][i];
        if(t) {
            for(int k = 1 ; k <= N ; ++k) {
            a.f[j][k] = inc(a.f[j][k],MOD - mul(t,a.f[i][k]));
            b.f[j][k] = inc(b.f[j][k],MOD - mul(t,b.f[i][k]));
            }
        }
        }
    }
    return b;
    }
    friend bool operator < (const Matrix &a,const Matrix &b) {
    for(int i = 1 ; i <= N ; ++i) {
        for(int j = 1 ; j <= N ; ++j) {
        if(a.f[i][j] != b.f[i][j]) return a.f[i][j] < b.f[i][j];
        }
    }
    return false;
    }
    friend bool operator == (const Matrix &a,const Matrix &b) {
    for(int i = 1 ; i <= N ; ++i) {
        for(int j = 1 ; j <= N ; ++j) {
        if(a.f[i][j] != b.f[i][j]) return false;
        }
    }
    return true;
    }
    void init() {
    for(int i = 1 ; i <= N ; ++i) {
        for(int j = 1 ; j <= N ; ++j) {
        read(f[i][j]);
        }
    }
    }
}A,B;
map<Matrix ,int> rec;
int BSGS(Matrix a,Matrix b) {
    int S = sqrt(MOD);
    Matrix t,ia,k;
    t.unit();k = b;ia = ~a;
    for(int i = 0 ; i < S ; ++i) {
    if(t == b && i) return i;
    t = t * a;
    if(!rec.count(k)) rec[k] = i;
    k = k * ia;
    }
    k = t;
    for(int i = 1 ; i * S <= MOD; ++i) {
    if(rec.count(k)) return i * S + rec[k];
    k = k * t;
    }
}
void Solve() {
    read(N);read(MOD);
    inv[1] = 1;
    for(int i = 2 ; i < MOD ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);
    A.init();B.init();
    out(BSGS(A,B));enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}

【BZOJ】4128: Matrix

原文：https://www.cnblogs.com/ivorysi/p/10090283.html