本文共 1231 字，大约阅读时间需要 4 分钟。
矩阵的BSGS。
只需要哈希一下存起来就可以了。
也并不需要求逆。
#include #include #include #include #include #include using namespace std; #define F(i,j,k) for (ll i=j;i<=k;++i)#define D(i,j,k) for (ll i=j;i>=k;--i)#define ll long long#define base 231#define basemd 1000000007 ll n,p; struct matrix{ ll x[80][80]; void init(){memset(x,0,sizeof x);} matrix operator * (matrix a){ matrix ret; ret.init(); F(i,1,n) F(j,1,n) { F(k,1,n) ret.x[i][j]=ret.x[i][j]+x[i][k]*a.x[k][j]; ret.x[i][j]%=p; } return ret; } ll encode() { ll ret=0; F(i,1,n) F(j,1,n) ret=(ret*base+x[i][j])%basemd; return ret; } void read() { F(i,1,n) F(j,1,n) scanf("%lld",&x[i][j]),x[i][j]%=p; } void build() {init();F(i,1,n)x[i][i]=1;}}A,B,E; map mp; void BSGS(){ mp.clear(); ll m=ceil(sqrt(p)); matrix ans; F(i,0,m) { if (i==0){ans=B;mp[ans.encode()]=i;continue;} ans=ans*A; mp[ans.encode()]=i; } matrix tmp=E; F(i,1,m) tmp=tmp*A; ans=E; F(i,1,m) { ans=ans*tmp; if (mp[ans.encode()]) { ll ret=i*m-mp[ans.encode()]; printf("%lld\n",(ret%p+p)%p); return ; } }} int main(){ scanf("%lld%lld",&n,&p); A.read();B.read();E.build(); BSGS();}
转载于:https://www.cnblogs.com/SfailSth/p/6582025.html