题目
给定矩阵A, B和模数p，求最小的正整数x满足 A^x = B(mod p).
分析
与整数的离散对数类似，只不过普通乘法换乘了矩阵乘法。
由于矩阵的求逆麻烦，使用 $A^{km-t} = B(mod \ p)$ 形式的BSGS。
然后就是判断矩阵是否相等，
一种方法是对矩阵进行Hash，
这里为了防止两个不同矩阵的Hash值冲突，使用了两个底数进行Hash。
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
typedef unsigned long long ull;
const ull base1 = , base2 = ; struct matrix
{
int r, c;
int mat[][];
ull h1, h2;
matrix(){
memset(mat, , sizeof(mat));
h1 = h2 = ; //记得初始化
} void Hash()
{
for(int i = ;i < r;i++)
for(int j = ;j < c;j++)
h1 = h1 * base1 + mat[i][j], h2 = h2 * base2 + mat[i][j];
}
};
int n, p;
matrix A, B; matrix mul(matrix A, matrix B) //矩阵相乘
{
matrix ret;
ret.r = A.r; ret.c = B.c;
for(int i = ;i < A.r;i++)
for(int k = ;k < A.c;k++)
for(int j = ;j < B.c;j++)
{
ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % p;
}
return ret;
} matrix mpow(matrix A, int n)
{
matrix ret;
ret.r = A.r; ret.c = A.c;
for(int i = ;i < ret.r;i++) ret.mat[i][i] = ;
while(n)
{
if(n & ) ret = mul(ret, A);
A = mul(A, A);
n >>= ;
}
return ret;
} map<pair<ull, ull>, int>mp;
int BSGS(matrix A, matrix B, int p)
{
int m=sqrt(p)+;mp.clear();
matrix res= B;
for(int i = ;i < m;i++)
{
res.Hash();
mp[make_pair(res.h1, res.h2)] = i;
res = mul(A, res);
}
matrix mi = mpow(A, m);
matrix tmp = mi;
for(int i = ;i <= m+;i++)
{
tmp.Hash();
pair<ull, ull> pa = make_pair(tmp.h1, tmp.h2);
if(mp.count(pa)) return i*m - mp[pa];
tmp = mul(tmp, mi);
}
} void debug_print(matrix a)
{
for(int i = ;i < a.r;i++)
{
for(int j = ;j < a.c;j++){
printf("%d ", a.mat[i][j]);
}
printf("\n");
}
} int main()
{
//srand(NULL);
scanf("%d%d", &n, &p);
A.r = A.c = n;
for(int i = ;i < n;i++)
for(int j = ;j < n;j++){
int tmp;
scanf("%d", &tmp);
A.mat[i][j] = tmp;
}
B.r = B.c = n;
for(int i = ;i < n;i++)
for(int j = ;j < n;j++){
int tmp;
scanf("%d", &tmp);
B.mat[i][j] = tmp;
} ///debug_print(A);
//debug_print(B);
//debug_print(R); printf("%d\n", BSGS(A, B, p));
}
另一种方法是随机产生一个n*1的矩阵f，若A*f=B*f我们则认为这两个矩阵是相等的。为了让直接map矩阵，还要写比较函数（奇怪的是，答案还受比较函数的影响）。
注意矩阵的左乘和右乘。
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
struct matrix
{
int r, c;
int mat[][];
matrix(){
memset(mat, , sizeof(mat));
} bool operator < (const matrix &w) const //???为什么会影响结果呢
{
for (int i=;i< r;i++)
if (mat[i][]<w.mat[i][]) return ;
else if (mat[i][]>w.mat[i][]) return ;
return ;
}
};
int n, p;
matrix A, B, R; //R是随机矩阵 matrix mul(matrix A, matrix B) //矩阵相乘
{
matrix ret;
ret.r = A.r; ret.c = B.c;
for(int i = ;i < A.r;i++)
for(int k = ;k < A.c;k++)
for(int j = ;j < B.c;j++)
{
ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % p;
}
return ret;
} matrix mpow(matrix A, int n)
{
matrix ret;
ret.r = A.r; ret.c = A.c;
for(int i = ;i < ret.r;i++) ret.mat[i][i] = ;
while(n)
{
if(n & ) ret = mul(ret, A);
A = mul(A, A);
n >>= ;
}
return ret;
} map<matrix, int>mp;
int BSGS(matrix A, matrix B, matrix R, int p)
{
int m=sqrt(p)+;mp.clear();
matrix res=mul(B, R);
for(int i = ;i < m;i++)
{
mp[res] = i;
res = mul(A, res);
}
matrix mi = mpow(A, m);
matrix tmp = mi;
for(int i = ;i <= m+;i++)
{
matrix t = mul(tmp, R);
if(mp.count(t)) return i*m - mp[t];
tmp = mul(tmp, mi);
}
} void debug_print(matrix a)
{
for(int i = ;i < a.r;i++)
{
for(int j = ;j < a.c;j++){
printf("%d ", a.mat[i][j]);
}
printf("\n");
}
} int main()
{
//srand(NULL);
scanf("%d%d", &n, &p);
A.r = A.c = n;
for(int i = ;i < n;i++)
for(int j = ;j < n;j++){
int tmp;
scanf("%d", &tmp);
A.mat[i][j] = tmp;
}
B.r = B.c = n;
for(int i = ;i < n;i++)
for(int j = ;j < n;j++){
int tmp;
scanf("%d", &tmp);
B.mat[i][j] = tmp;
} R.r = n, R.c = ;
for(int i = ;i < n;i++) R.mat[i][] = rand()%(p-) + p; ///debug_print(A);
//debug_print(B);
//debug_print(R); printf("%d\n", BSGS(A, B, R, p));
}
参考链接：