题目大意：给定两个 保证内有解 这个问题类似于离散对数问题，因此可以用BSGS来解决 但是和离散对数要求逆元一样，这个问题需要求出矩阵的逆 之前一直只会 做法如下： 将 然后通过初等行变换将左侧的 此时右侧的单位矩阵 (其实和高斯消元解线性方程组是一样的，只不过把右侧的答案列向量变成了单位矩阵) 然后就简单了- – (像我这种连BSGS都写不对的傻逼赶紧退役吧
;int n,p,inv[20000];inline void Assert(bool flag){if(flag) return ;while(1) puts(“Fuck♂You!”);}struct Matrix{int a[M][M];Matrix() {}Matrix(bool flag){memset(a,0,sizeof a);int i;for(i=1;i<=n;i++)a[i][i]=flag;}int* operator [] (int x){return a[x];}== (Matrix x,Matrix y){int i,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(x[i][j]!=y[i][j])return false;return true;}friend Matrix operator * (Matrix x,Matrix y){Matrix z(0);int i,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)(z[i][j]+=x[i][k]*y[k][j])%=p;return z;}friend Matrix Inverse(Matrix a)//We assume that the matrix x is inversible{Matrix re(true);int i,j,k;for(i=1;i<=n;i++){for(k=i;k<=n;k++)if(a[k][i])break;Assert(k!=n+1);for(j=1;j<=n;j++){swap(a[i][j],a[k][j]);swap(re[i][j],re[k][j]);}int inv=::inv[a[i][i]];for(j=1;j<=n;j++){(a[i][j]*=inv)%=p;(re[i][j]*=inv)%=p;}for(k=1;k<=n;k++)if(k!=i){int temp=(p-a[k][i])%p;for(j=1;j<=n;j++){(a[k][j]+=temp*a[i][j])%=p;(re[k][j]+=temp*re[i][j])%=p;}}}return re;}int Hash(){int i,j,re=0;for(i=1;i<=n;i++){long long temp=0;for(j=1;j<=n;j++)temp=(temp*BASE1+a[i][j])%MOD;re=((long long)re*BASE2+temp)%MOD;}return re;}}A,B;namespace Hash_Table{struct List{Matrix x;int val;List *next;List(Matrix _,List *__):x(_),val(0x3f3f3f3f),next(__) {}}*head[1001001];int& Hash(Matrix x){int pos=x.Hash();List *temp;for(temp=head[pos];temp;temp=temp->next)if(temp->x==x)return temp->val;return (head[pos]=new List(x,head[pos]))->val;}}void Linear_Shaker(){int i;for(inv[1]=1,i=2;i<p;i++)inv[i]=(p-p/i)*inv[p%i]%p;}int Baby_Step_Giant_Step(){int i,m=ceil(sqrt(p))+1;Matrix D(true);for(i=0;i<m;i++,D=D*A){int &val=Hash_Table::Hash(D);val=min(val,i);}Matrix temp(true);for(i=0;i<=m;i++,temp=temp*D){Matrix X=Inverse(temp)*B;int &val=Hash_Table::Hash(X);if(val!=0x3f3f3f3f)return i*m+val;}Assert(false);}int main(){int i,j;cin>>n>>p;Linear_Shaker();for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf(“%d”,&A[i][j]);for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf(“%d”,&B[i][j]);cout<<Baby_Step_Giant_Step()<<endl;return 0;}
，我不但的回首，伫足，然后时光扔下我轰轰烈烈的向前奔去。
