1. 개요
문제 링크다이아 5, 선형대수학, 무작위화
A×B=C를 만족하는 겹치지 않는 부분행렬의 최대개수
2. 접근
- Freivald's algorithm을 사용하는 세 문제 중 두 번째. 다이아 하위 문제는 보통 새로운
어려운알고리즘을 사용하는 문제가 많은 것 같다. 그래봐야 전체 2700개 다이아 문제 중 7개 풀었지만 내 좁은 시야에서는 암튼 그렇다. - 문제로 돌아오자. 우선 정수범위가 터질 수 있으니 long long을 사용하고, N이 256이고, L이 4000에서 100만정도 되므로 시간을 잘 관리해야 한다. O(N^3)에 하면 무조건 터지므로 O(kN^2)에 A×B=C를 유사하게 검증할 수 있는 프리발즈 알고리즘을 사용한다.
- 다음으로 0부터 L까지 돌면서 개수를 세어주면 되는데, 앞에서부터 그냥 세어주면 된다. 왜냐?
- 만약 [i,i+3×N]사이의 j에 대해서 [j,j+3×N]이 조건을 만족한다고 생각하면, j를 선택하는 것은 손해이다.
- 왜냐하면 [i+3×N,j+3×N] 사이의 조건을 만족하는 k를 놓칠 수 있기 때문이다.
- 그래서 이 문제가 그리디 문제가 된다. 그리디한 인간은 앞에서부터 하나씩 찾아가기 때문이다.
- 나머지는 입력 최적화해주고, 크게 복잡할 것은 없다.
3. Pseudo code
bool freivald(int x) {
A = matrix[x ~x + N];
B = matrix[x + N ~x + 2 * N];
C = matrix[x + 2 * N ~x + 3 * N];
int random = 25;
// 25 -> 1450ms
// 30 -> 1700ms
// 50 -> 2700ms
while (random--)
r = rand(N);
if (A * (B * r) != C * r) return 0;
return 1;
}
count = 0;
for (x = 0 ~L - 3 * N) // 3*N만큼 뒤를 보기 때문에
if (freivald(x))
x += 3 * N; // i++ 때문에 3*N-1
count++;
return count * (N * N * 3)4. Source code
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
using namespace std;
#define ist istream&
using ld = long long;
typedef vector<ld> vld;
int n, l;
struct mat {
vector<vld> a;
void init(int n, int l) {
a = vector<vld>(n, vld(l, 0));
}
vld operator*(vld m) {
vld c(n, 0);
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
c[i] += a[i][k] * m[k];
return c;
}
} m;
ist operator>>(ist in, mat& a) {
for (int i = 0; i < n; i++)
for (int j = 0; j < l; j++)
in >> a.a[i][j];
return in;
}
mat a, b, c;
vld r;
bool freivald(int x) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
a.a[i][j] = m.a[i][x + j];
b.a[i][j] = m.a[i][x + n + j];
c.a[i][j] = m.a[i][x + 2 * n + j];
}
int R = 25;
while (R--) {
for (auto& x : r) x = rand() % 2;
if (a * (b * r) != c * r) return 0;
}
return 1;
}
int main() {
srand(time(0));
cin.tie(0)->ios_base::sync_with_stdio(0);
cin >> n >> l;
m.init(n, l);
a.init(n, n), b.init(n, n), c.init(n, n);
r.resize(n);
cin >> m;
int cnt = 0;
for (int i = 0; i <= l - 3 * n; i++)
if (freivald(i)) i += 3 * n - 1, cnt += n * n * 3;
cout << cnt;
}