BZOJ4128Matrix——hash+矩阵乘法+BSGS

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define pr pair<ull,ull>
using namespace std;
int base1=10007;
int base2=233;
int n,p,m;
map<pr,int>mp;
struct lty
{
	ull v[80][80],val1,val2;
	lty(int x)
	{
		memset(v,0,sizeof(v));
		val1=val2=0;
		for(int i=1;i<=n;i++)
		{
			v[i][i]=x;
		}
	}
	lty operator *(lty a)
	{
		lty ans(0);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=n;k++)
				{
					ans.v[i][j]=(ans.v[i][j]+v[i][k]*a.v[k][j])%p;
				}
			}
		}
		return ans;
	}
	void hash()
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				val1=val1*base1+v[i][j];
				val2=val2*base2+v[i][j];
			}
		}
	}
};
int main()
{
	scanf("%d%d",&n,&p);
	m=ceil(sqrt(p));
	lty A(0),B(0),C(1),D(1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%llu",&A.v[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%llu",&B.v[i][j]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		B=B*A;
		B.hash();
		mp[make_pair(B.val1,B.val2)]=i;
	}
	for(int i=1;i<=m;i++)
	{
		C=C*A;
	}
	for(int i=1;i<=m;i++)
	{
		D=D*C;
		D.hash();
		if(mp.find(make_pair(D.val1,D.val2))!=mp.end())
		{
			printf("%d",i*m-mp[make_pair(D.val1,D.val2)]);
			return 0;
		}
	}
}