题面

给定矩阵A,B和模数p,求最小的x满足

A^x = B (mod p)

思路

一眼看去就是BSGS，很显然这个结论在矩阵中也同样适用，那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单)

代码

#include<bits/stdc++.h>
#define LL long long
#define Mod 998244353 
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
map<LL,LL> m;
LL n,p,A[75][75],B[75][75],C[75][75],D[75][75],E[75][75];
inline void mul(LL X[75][75],LL Y[75][75],LL Z[75][75])
{
	LL tmp[75][75];memset(tmp,0,sizeof(tmp));
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++)for (LL k=1;k<=n;k++)tmp[i][j]+=(X[i][k]*Y[k][j])%p;tmp[i][j]%=p;
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++) Z[i][j]=tmp[i][j];
}
inline LL Hash(LL X[75][75])
{
	LL Sum=0;
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++)Sum=(Sum+X[i][j]*i+j)%Mod;
	return Sum;
}
inline LL BSGS(LL X[75][75],LL Y[75][75],LL p)
{
	LL len=(LL)ceil(sqrt(p));
	m[Hash(Y)]=0;
	for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) C[i][j]=Y[i][j],D[i][j]=X[i][j];
	for (LL i=1;i<=len;i++) mul(X,C,C),m[Hash(C)]=i;
	for (LL i=1;i<len;i++) mul(X,D,D);
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) E[i][j]=D[i][j];
	for (LL i=1;i<len;i++) {if (m.count(Hash(E))) return i*len-m[Hash(E)];mul(D,E,E);}
}
int main()
{
	read(n),read(p);
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++) read(A[i][j]);
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++) read(B[i][j]);
	cout<<BSGS(A,B,p)<<endl;
	return 0;
}