【bzoj4128】Matrix 矩阵乘法+Hash+BSGS

题目描述

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

A^x = B (mod p)

输入

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

输出

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

样例输入

2 7
1 1
1 0
5 3
3 2

样例输出

题解

矩阵乘法+Hash+BSGS

看到题目很容易想到BSGS算法，但要求逆元，而矩阵的逆不是很好求出，怎么办？

事实上，BSGS有两种形式：$a^{km+t}\equiv(mod\ p)$和$a^{km-t}\equiv b(mod\ p)$

第一种形式是经典的BSGS，并可以应用到EXBSGS中，而第二种形式的优点在于不需要求逆元，放到此题中就是不需要求矩阵的逆。

按照BSGS的思路，原题可化为$A^{km}\equiv B*A^t(mod\ p)$

于是我们便可以把$B*A^t(mod\ p)$存到map中，然后枚举k的取值来查询。

如何快速查询？就需要使用Hash。

这里为了防止两个不同矩阵的Hash值冲突，使用了两个底数进行Hash。

然后就可以愉快的套BSGS的板子了~

#include <cstdio>

#include <cmath>

#include <cstring>

#include <map>

#include <utility>

#define N 75

using namespace std;

typedef unsigned long long ull;

const ull base1 = 100003 , base2 = 1000003;

int n , p;

struct data

{

	ull v[N][N] , val1 , val2;

	data(int x)

	{

		int i;

		memset(v , 0 , sizeof(v)) , val1 = val2 = 0;

		for(i = 1 ; i <= n ; i ++ ) v[i][i] = x;

	}

	data operator*(const data a)const

	{

		int i , j , k;

		data ans(0);

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

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

				for(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()

	{

		int i , j;

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

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

				val1 = val1 * base1 + v[i][j] , val2 = val2 * base2 + v[i][j];

	}

};

map<pair<ull , ull> , int> f;

map<pair<ull , ull> , int>::iterator it;

int main()

{

	int i , j , k , m;

	scanf("%d%d" , &n , &p) , m = (int)ceil(sqrt(p));

	data A(0) , B(0) , C(1) , D(1);

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

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

	for(i = 1 ; i <= m ; i ++ ) B = B * A , B.hash() , f[make_pair(B.val1 , B.val2)] = i;

	for(i = 1 ; i <= m ; i ++ ) C = C * A;

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

	{

		D = D * C , D.hash() , it = f.find(make_pair(D.val1 , D.val2));

		if(it != f.end())

		{

			printf("%d\n" , i * m - it->second);

			return 0;

		}

	}

	return 0;

}

巴特西

【bzoj4128】Matrix 矩阵乘法+Hash+BSGS

最新文章

热门文章