BZOJ4128 Matrix Matrix BSGS

Question Portal

https://lydsy.com/JudgeOnline/problem.php?id=4128

Problem solution

I thought about it for ten minutes without any thoughts.

Then I caught a glimpse of the sentence “The data is guaranteed to be solved in \(p\)“, and \(p ​​\leq 19997\)…

Then this question is to replace the numbers in the congruence class BSGS with a matrix.

The problem is how to quickly determine whether two matrices are equal. Hash chant.

Then there is no more.

It is recommended to write a version of BSGS that does not require inversion.

#include#include#define fec(i, x, y) (int i = head[x], y = g [i].to; i; i = g[i].ne, y = g[i].to)#define dbg(...) fprintf(stderr, __VA_ARGS__)#define File(x) freopen(#x ".in", "r", stdin), freopen(#x".out", "w", stdout)#define fi first#define se second#define pb push_backtemplate inline char smax( A &a, const B &b) {return a  inline char smin(A &a, const B &b) {return b  pii;template inline void read(I &x) {int f = 0, c; while (!isdigit(c = getchar())) c =='-'? f = 1: 0; x = c & 15; while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15); f? x = -x: 0;)const int N = 70 + 7;const int base = 1997;int n, P;std::tr1::unordered_map< ull, int> mp;inline int smod(int x) {return x >= P? x-P: x; }inline void sadd(int &x, c onst int &y) {x += y; x >= P? x -= P: x; }inline int fpow(int x, int y) {int ans = 1; for (; y; y >>= 1, x = (ll)x * x% P) if (y & 1) ans = (ll)ans * x% P; return ans;}struct Matrix {int a[N][N]; inline Matrix() {memset (a, 0, sizeof(a));} inline Matrix(const int &x) {memset(a, 0, sizeof(a)); for (int i = 1; i <= n; ++i) a[ i][i] = x;} inline Matrix operator * (const Matrix &b) {Matrix c; for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) sadd(ca[i][j], (ll)a[i][k] * ba[k][j]% P ); return c;} inline ull hash() {ull ha = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) ha = ha * base + (a[i][j] + 1); return ha; }) A, B;inline Matrix fpow(Matrix x, int y) {Matrix ans(1); for (; y; y> >= 1, x = x * x) if (y & 1) ans = ans * x; return ans;}inline int bsgs() {int m = sq rt(P); Matrix C = B, e; for (int i = 0; i