BZOJ 4128 Matrix

题目大意

给你矩阵$A,B$，模数$p$（质数），求最小的$x$满足$A ^ x = B (\text{mod }p)$.

普通的BSGS即可。重载一下矩阵的乘，幂两个符号之后就可以和数一样进行操作了。

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
int n,p,m;
struct matrix
{
	int v[80][80];ull hsh;
	int *operator[](int x){return v[x];}
	matrix(){memset(v,0,sizeof v);}
	void init()
	{
		memset(v,0,sizeof v);
		for(int i=1;i<=n;++i) v[i][i]=1;
		genhsh();
	}
	void genhsh()
	{
		hsh=0;
		int i,j;
		for(i=1;i<=n;++i)
			for(j=1;j<=n;++j)
				hsh=hsh*131+v[i][j];
	}
	matrix operator*(matrix &tg)
	{
		matrix ret;
		int i,j,k;
		for(k=1;k<=n;++k)
			for(i=1;i<=n;++i)
				for(j=1;j<=n;++j)
					ret[i][j]=(ret[i][j]+v[i][k]*tg[k][j])%p;
		ret.genhsh();
		return ret;
	}
	matrix operator^(int tg)
	{
		matrix ret,tmp=*this;
		ret.init();
		while(tg)
		{
			if(tg&1) ret=ret*tmp;
			tmp=tmp*tmp,tg>>=1;
		}
		ret.genhsh();
		return ret;
	}
}a,b;
map<ull,int>mp;
int main()
{
	scanf("%d%d",&n,&p),m=ceil(sqrt(p));
	int i,j;matrix t,tt;map<ull,int>::iterator it;
	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]);
	a.genhsh(),b.genhsh();
	for(i=0,t=b;i<m;++i,t=t*a)
		if(mp.find(t.hsh)==mp.end())
			mp[t.hsh]=i;
	for(i=1,t=tt=a^m;i<=m;++i,t=t*tt)
	{
		it=mp.find(t.hsh);
		if(it!=mp.end())
			printf("%d\n",i*m-it->second),exit(0);
	}
	return 0;
}