2 条题解

  • 0
    @ 2025-10-8 17:09:53 
    #include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pdi pair<db, int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
// #define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template <class T>
void read(T &res)
{
	res = 0;
	char c = getchar();
	T f = 1;
	while (c < '0' || c > '9')
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template <class T>
void out(T x)
{
	if (x < 0)
	{
		x = -x;
		putchar('-');
	}
	if (x >= 10)
	{
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int MOD, N;
int inv[20005];
int inc(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a, int b)
{
	return a * b % MOD;
}
struct Matrix
{
	int f[72][72];
	Matrix() { memset(f, 0, sizeof(f)); }
	friend Matrix operator*(const Matrix &a, const Matrix &b)
	{
		Matrix c;
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				for (int k = 1; k <= N; ++k)
				{
					c.f[i][j] = inc(c.f[i][j], mul(a.f[i][k], b.f[k][j]));
				}
			}
		}
		return c;
	}
	void unit()
	{
		for (int i = 1; i <= N; ++i)
			f[i][i] = 1;
	}
	friend Matrix operator~(Matrix a)
	{
		Matrix b;
		b.unit();
		for (int i = 1; i <= N; ++i)
		{
			int l;
			for (l = i; l <= N; ++l)
			{
				if (a.f[l][i])
					break;
			}
			if (l != i)
			{
				for (int j = 1; j <= N; ++j)
				{
					swap(a.f[l][j], a.f[i][j]);
					swap(b.f[l][j], b.f[i][j]);
				}
			}
			int t = inv[a.f[i][i]];
			if (t)
			{
				for (int j = 1; j <= N; ++j)
				{

					a.f[i][j] = mul(a.f[i][j], t);
					b.f[i][j] = mul(b.f[i][j], t);
				}
			}
			for (int j = 1; j <= N; ++j)
			{
				if (j == i)
					continue;
				int t = a.f[j][i];
				if (t)
				{
					for (int k = 1; k <= N; ++k)
					{
						a.f[j][k] = inc(a.f[j][k], MOD - mul(t, a.f[i][k]));
						b.f[j][k] = inc(b.f[j][k], MOD - mul(t, b.f[i][k]));
					}
				}
			}
		}
		return b;
	}
	friend bool operator<(const Matrix &a, const Matrix &b)
	{
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				if (a.f[i][j] != b.f[i][j])
					return a.f[i][j] < b.f[i][j];
			}
		}
		return false;
	}
	friend bool operator==(const Matrix &a, const Matrix &b)
	{
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				if (a.f[i][j] != b.f[i][j])
					return false;
			}
		}
		return true;
	}
	void init()
	{
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				read(f[i][j]);
			}
		}
	}
} A, B;
map<Matrix, int> rec;
int BSGS(Matrix a, Matrix b)
{
	int S = sqrt(MOD);
	Matrix t, ia, k;
	t.unit();
	k = b;
	ia = ~a;
	for (int i = 0; i < S; ++i)
	{
		if (t == b && i)
			return i;
		t = t * a;
		if (!rec.count(k))
			rec[k] = i;
		k = k * ia;
	}
	k = t;
	for (int i = 1; i * S <= MOD; ++i)
	{
		if (rec.count(k))
			return i * S + rec[k];
		k = k * t;
	}
}
void Solve()
{
	read(N);
	read(MOD);
	inv[1] = 1;
	for (int i = 2; i < MOD; ++i)
		inv[i] = mul(inv[MOD % i], MOD - MOD / i);
	A.init();
	B.init();
	out(BSGS(A, B));
	enter;
}
int main()
{
#ifdef ivorysi
	freopen("f1.in", "r", stdin);
#endif
	Solve();
	return 0;
}
    • 0
      @ 2025-10-8 17:09:42 
      #include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pdi pair<db, int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
// #define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template <class T>
void read(T &res)
{
	res = 0;
	char c = getchar();
	T f = 1;
	while (c < '0' || c > '9')
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template <class T>
void out(T x)
{
	if (x < 0)
	{
		x = -x;
		putchar('-');
	}
	if (x >= 10)
	{
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int MOD, N;
int inv[20005];
int inc(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a, int b)
{
	return a * b % MOD;
}
struct Matrix
{
	int f[72][72];
	Matrix() { memset(f, 0, sizeof(f)); }
	friend Matrix operator*(const Matrix &a, const Matrix &b)
	{
		Matrix c;
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				for (int k = 1; k <= N; ++k)
				{
					c.f[i][j] = inc(c.f[i][j], mul(a.f[i][k], b.f[k][j]));
				}
			}
		}
		return c;
	}
	void unit()
	{
		for (int i = 1; i <= N; ++i)
			f[i][i] = 1;
	}
	friend Matrix operator~(Matrix a)
	{
		Matrix b;
		b.unit();
		for (int i = 1; i <= N; ++i)
		{
			int l;
			for (l = i; l <= N; ++l)
			{
				if (a.f[l][i])
					break;
			}
			if (l != i)
			{
				for (int j = 1; j <= N; ++j)
				{
					swap(a.f[l][j], a.f[i][j]);
					swap(b.f[l][j], b.f[i][j]);
				}
			}
			int t = inv[a.f[i][i]];
			if (t)
			{
				for (int j = 1; j <= N; ++j)
				{

					a.f[i][j] = mul(a.f[i][j], t);
					b.f[i][j] = mul(b.f[i][j], t);
				}
			}
			for (int j = 1; j <= N; ++j)
			{
				if (j == i)
					continue;
				int t = a.f[j][i];
				if (t)
				{
					for (int k = 1; k <= N; ++k)
					{
						a.f[j][k] = inc(a.f[j][k], MOD - mul(t, a.f[i][k]));
						b.f[j][k] = inc(b.f[j][k], MOD - mul(t, b.f[i][k]));
					}
				}
			}
		}
		return b;
	}
	friend bool operator<(const Matrix &a, const Matrix &b)
	{
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				if (a.f[i][j] != b.f[i][j])
					return a.f[i][j] < b.f[i][j];
			}
		}
		return False;
	}
	friend bool operator==(const Matrix &a, const Matrix &b)
	{
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				if (a.f[i][j] != b.f[i][j])
					return False;
			}
		}
		return True;
	}
	void init()
	{
		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				read(f[i][j]);
			}
		}
	}
} A, B;
map<Matrix, int> rec;
int BSGS(Matrix a, Matrix b)
{
	int S = sqrt(MOD);
	Matrix t, ia, k;
	t.unit();
	k = b;
	ia = ~a;
	for (int i = 0; i < S; ++i)
	{
		if (t == b && i)
			return i;
		t = t * a;
		if (!rec.count(k))
			rec[k] = i;
		k = k * ia;
	}
	k = t;
	for (int i = 1; i * S <= MOD; ++i)
	{
		if (rec.count(k))
			return i * S + rec[k];
		k = k * t;
	}
}
void Solve()
{
	read(N);
	read(MOD);
	inv[1] = 1;
	for (int i = 2; i < MOD; ++i)
		inv[i] = mul(inv[MOD % i], MOD - MOD / i);
	A.init();
	B.init();
	out(BSGS(A, B));
	enter;
}
int main()
{
#ifdef ivorysi
	freopen("f1.in", "r", stdin);
#endif
	Solve();
	return 0;
}
      • 1

      *【BSGS】矩阵 $A^x ≡ B(\mod p)$

      信息

      ID
      5793
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      2
      已通过
      1
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 6ms
      4. Powered by Hydro v5.0.1 Community