题解
学习一下矩阵求逆
就是我们考虑这个矩阵
\(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;
- }
来源: http://www.bubuko.com/infodetail-2877879.html