백준13165 이것도 해결해 보시지

작성일 | In

문제 링크

  • http://icpc.me/13165

사용 알고리즘

  • 랜덤

시간복잡도

  • $O(N^2M)$

풀이

두 정사각행렬 $A, B$와 두 행렬을 곱한 결과 $C$가 주어졌을 때 곱셈이 올바르게 수행되었는지 $O(N^2)$ 랜덤 알고리즘은 잘 알려져 있습니다. 알고리즘을 간단하게 요약하자면, 랜덤한 $N\times 1$ 행렬 $V$를 만들어서 $A\times (BV) = CV$인지 확인하면 곱셈을 올바르게 수행했는지 높은 확률로 판별할 수 있습니다.

Freivalds’ Algorithm을 알고 있다면, 이 문제는 간단한 그리디로 해결할 수 있는 스케줄링 문제로 바뀌게 됩니다.

$N\times N$행렬과 $N\times 1$행렬을 곱하는 부분을 조금 신경써서 구현하면 컴파일러가 SIMD로 최적화를 해주기 때문에 매우 빠르게 동작합니다. 자세한 구현은 아래 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;

int N, M;
alignas(32) uint A[1024000], R1[256], R2[256], R3[256], R[256];
mt19937 Gen((unsigned)chrono::steady_clock::now().time_since_epoch().count());

bool Test(int st){
    for(int i=0; i<N; i++){
        R1[i] = 0;
        for(int j=0; j<N; j++) R1[i] += A[i*M+st+N+j] * R[j];
    }
    for(int i=0; i<N; i++){
        R2[i] = 0;
        for(int j=0; j<N; j++) R2[i] += A[i*M+st+j] * R1[j];
    }
    for(int i=0; i<N; i++){
        R3[i] = 0;
        for(int j=0; j<N; j++) R3[i] += A[i*M+st+N+N+j] * R[j];
    }
    bool res = true;
    for(int i=0; i<N; i++) res &= R2[i] == R3[i];
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=0; i<N*M; i++) cin >> A[i];
    for(int i=0; i<N; i++) R[i] = Gen() & 65535;

    int lst = 0, cnt = 0;
    for(int i=0; i+N*3<=M; i++){
        if(Test(i)) cnt++, lst = i = i + N*3 - 1;
    }
    cout << cnt * N * N * 3;
}