【BZOJ4128】Matrix

Description

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

A^x = B (mod p)

Input

第一行两个整数n和p，表示矩阵的阶和模数,接下来一个n * n的矩阵A.接下来一个n * n的矩阵B

Output

输出一个正整数，表示最小的可能的x，数据保证在p内有解

Sample Input

2 7
1 1
1 0
5 3
3 2

Sample Output

HINT

对于100%的数据，n <= 70,p <=19997，p为质数,0<= A_{ij},B_{ij}< p

保证A有逆

题解：网上看到好多求矩阵的逆的，一定是BSGS的姿势不对吧~

在BSGS时令x=i*m-j，就变成了$A^{i\times m}=BA^{j} (mod\ p)$，然后将矩阵hash一下扔到map里就行啦~

#include <cstdio>

#include <iostream>

#include <cstring>

#include <map>

#include <cmath>

using namespace std;

typedef unsigned long long ull;

int n,m,p;

ull s1[80],s2[80];

map<ull,int> mp;

struct M

{

	int v[80][80];

	ull hs;

	M (){memset(v,0,sizeof(v)),hs=0;}

	ull hash()

	{

		if(hs)	return hs;

		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	hs+=s1[i-1]*s2[j-1]*v[i][j];

		return hs;

	}

	M operator * (M a) 	const

	{

		M b;

		int i,j,k;

		for(i=1;i<=n;i++)

			for(j=1;j<=n;j++)

				for(k=1;k<=n;k++)

					b.v[i][j]=(b.v[i][j]+v[i][k]*a.v[k][j])%p;

		return b;

	}

};

M I,A,B,x,y;

int main()

{

	scanf("%d%d",&n,&p);

	int i,j;

	for(s1[0]=s2[0]=1,i=1;i<=n;i++)	s1[i]=s1[i-1]*233,s2[i]=s2[i-1]*2333;

	for(i=1;i<=n;i++)	for(j=1;j<=n;j++)	scanf("%d",&A.v[i][j]),I.v[i][j]=(i==j);

	for(i=1;i<=n;i++)	for(j=1;j<=n;j++)	scanf("%d",&B.v[i][j]);

	x=y=I,mp[x.hash()]=0;

	m=ceil(sqrt((double)p));

	for(i=1;i<=m;i++)	x=x*A,mp[(B*x).hash()]=i;

	for(i=1;i<=m;i++)

	{

		y=y*x;

		if(mp.find(y.hash())!=mp.end())

		{

			printf("%d",i*m-mp[y.hash()]);

			return 0;

		}

	}

}

BSGS