BZOJ4128 Matrix矩阵BSGS模板题

题面

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

A^x = B (mod p)

思路

一眼看去就是BSGS,很显然这个结论在矩阵中也同样适用,那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单)

代码

#include<bits/stdc++.h>
#define LL long long
#define Mod 998244353 
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
map<LL,LL> m;
LL n,p,A[75][75],B[75][75],C[75][75],D[75][75],E[75][75];
inline void mul(LL X[75][75],LL Y[75][75],LL Z[75][75])
{
	LL tmp[75][75];memset(tmp,0,sizeof(tmp));
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++)for (LL k=1;k<=n;k++)tmp[i][j]+=(X[i][k]*Y[k][j])%p;tmp[i][j]%=p;
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++) Z[i][j]=tmp[i][j];
}
inline LL Hash(LL X[75][75])
{
	LL Sum=0;
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++)Sum=(Sum+X[i][j]*i+j)%Mod;
	return Sum;
}
inline LL BSGS(LL X[75][75],LL Y[75][75],LL p)
{
	LL len=(LL)ceil(sqrt(p));
	m[Hash(Y)]=0;
	for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) C[i][j]=Y[i][j],D[i][j]=X[i][j];
	for (LL i=1;i<=len;i++) mul(X,C,C),m[Hash(C)]=i;
	for (LL i=1;i<len;i++) mul(X,D,D);
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) E[i][j]=D[i][j];
	for (LL i=1;i<len;i++) {if (m.count(Hash(E))) return i*len-m[Hash(E)];mul(D,E,E);}
}
int main()
{
	read(n),read(p);
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++) read(A[i][j]);
	for (LL i=1;i<=n;i++)for (LL j=1;j<=n;j++) read(B[i][j]);
	cout<<BSGS(A,B,p)<<endl;
	return 0;
} 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇