首页 > 代码库 > 【bzoj4128】Matrix 矩阵乘法+Hash+BSGS

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

2024-10-09 04:44:39   213人阅读

题目描述

给定矩阵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

样例输出

4

题解

矩阵乘法+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 75using 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


联系
我们