QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#480377 | #7618. Pattern Search | ucup-team052# | WA | 0ms | 3912kb | C++14 | 3.4kb | 2024-07-16 15:02:20 | 2024-07-16 15:02:20 |
Judging History
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'