QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480377#7618. Pattern Searchucup-team052#WA 0ms3912kbC++143.4kb2024-07-16 15:02:202024-07-16 15:02:20

Judging History

This is the latest submission verdict.

  • [2024-07-16 15:02:20]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3912kb
  • [2024-07-16 15:02:20]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const int md = 1e9 + 7;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) {
	return 1ull * x * y % md;
}

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

const int N = 2005;

mt19937_64 rng(0);
int a[N][N], b[N][N], ans[N][N], r[N], c[N], rnd[N], res1[N], res2[N];
int n;

void mul1(int *a, int b[N][N], int *res) {
	for (int i = 1; i <= n; i++) {
		res[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			res[j] = add(res[j], mul(a[i], b[i][j]));
		}
	}
}

void mul2(int a[N][N], int *b, int *res) {
	for (int i = 1; i <= n; i++) {
		res[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			res[i] = add(res[i], mul(a[i][j], b[j]));
		}
	}
}

int vis[N];
int mat[25][N], coef[25][25], res[25], y[N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &b[i][j]);
			ans[i][j] = b[i][j];
		}
	}
	for (int _ = 1; _ <= 3; _++) {
		for (int i = 1; i <= n; i++) rnd[i] = rng() % (md - 1) + 1;
		mul1(rnd, a, res1); mul1(res1, b, res2);
		for (int i = 1; i <= n; i++) {
			if (rnd[i] != res2[i]) c[i] = 1;
		}
		for (int i = 1; i <= n; i++) rnd[i] = rng() % (md - 1) + 1;
		mul2(a, rnd, res1); mul2(b, res1, res2);
		for (int i = 1; i <= n; i++) {
			if (rnd[i] != res2[i]) r[i] = 1;
		}
	}
	for (int j = 1; j <= n; j++) {
		if (!c[j]) continue;
		int m = 0;
		for (int i = 1; i <= n; i++) {
			if (r[i]) {
				++m;
				assert(m < 25);
				for (int k = 1; k <= n; k++) mat[m][k] = a[i][k];
			}
		}
		for (int i = 1; i <= n; i++) res1[i] = b[i][j];
		mul2(a, res1, res2);
		for (int i = 1; i <= n; i++) y[i] = sub(0, res2[i]);
		y[j] = add(y[j], 1);
		// for (int i = 1; i <= n; i++) y[i] = (i == j);
		memset(vis, 0, sizeof(vis));
		memset(coef, 0, sizeof(coef));
		for (int i = 1; i <= m; i++) {
			coef[i][i] = 1;
			for (int j = 1; j <= n; j++) {
				if (mat[i][j]) {
					if (!vis[j]) {
						vis[j] = i;
						break;
					}
					int cc = mul(mat[i][j], fpow(mat[vis[j]][j], md - 2));
					for (int k = j; k <= n; k++) mat[i][k] = sub(mat[i][k], mul(cc, mat[vis[j]][k]));
					for (int k = 1; k <= m; k++) coef[i][k] = sub(coef[i][k], mul(cc, coef[vis[j]][k]));
				}
			}
		}
		memset(res, 0, sizeof(res));
		for (int i = 1; i <= n; i++) {
			if (vis[i]) {
				int cc = mul(y[i], fpow(mat[vis[i]][i], md - 2));
				for (int j = i; j <= n; j++) y[j] = sub(y[j], mul(cc, mat[vis[i]][j]));
				for (int j = 1; j <= m; j++) res[j] = add(res[j], mul(cc, coef[vis[i]][j]));
			}
		}
		m = 0;
		for (int i = 1; i <= n; i++) {
			if (r[i]) {
				++m;
				ans[i][j] = add(ans[i][j], res[m]);
				// ans[i][j] = res[m];
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (b[i][j] != ans[i][j]) {
				++cnt;
			}
		}
	}
	printf("%d\n", cnt);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (b[i][j] != ans[i][j]) {
				printf("%d %d %d\n", i, j, ans[i][j]);
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3912kb

input:

2
bajkaaall aal
abca cba

output:

0

result:

wrong answer 1st numbers differ - expected: '2', found: '0'