BZOJ_4128_Matrix_矩阵乘法+哈希+BSGS
Description
给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p)
Input
第一行两个整数n和p，表示矩阵的阶和模数,接下来一个n * n的矩阵A.接下来一个n * n的矩阵B
Output
输出一个正整数，表示最小的可能的x，数据保证在p内有解
Sample Input
2 7
1 1
1 0
5 3
3 2
1 1
1 0
5 3
3 2
Sample Output
4
HINT
对于100%的数据，n <= 70,p <=19997，p为质数,0<= A_{ij},B_{ij}< p
保证A有逆
把矩阵哈希，然后把它当成一个数一样做BSGS。
就是正常的乘法换成了矩乘。
然后因为矩阵的逆元我不会求，于是这里用的$a^{mp-q}$\%$n=b$这种形式
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef unsigned long long ull;
ull base=13131;
int n,p;
map<ull,int>f;
struct Mat {
ull v[75][75],val;
Mat(){memset(v,0,sizeof(v)); val=0;}
Mat operator*(const Mat &x) const {
Mat re;int i,j,k;
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
for(k=1;k<=n;k++) {
(re.v[i][j]+=v[i][k]*x.v[k][j])%=p;
}
}
}
return re;
}
void hh() {
int i,j;
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
val=val*base+v[i][j];
}
}
}
}A,B;
int main() {
scanf("%d%d",&n,&p);
int i,m=(int)ceil(sqrt(p)),j;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%llu",&A.v[i][j]);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%llu",&B.v[i][j]);
A.hh(); B.hh();
Mat I;
for(i=1;i<=m;i++) {
B=B*A;
B.hh();
f[B.val]=i;
}
Mat D;for(i=1;i<=n;i++) D.v[i][i]=1;
for(i=1;i<=m;i++) D=D*A;
for(i=1;i<=n;i++) I.v[i][i]=1;
for(i=1;i<=m;i++) {
I=I*D;
I.hh();
ull tmp=I.val;
if(f.count(tmp)) {
printf("%d\n",i*m-f[tmp]);return 0;
}
}
}