BOJ 3847 : Comparing answers

알고리즘

random

시간복잡도

$O(TKN^2)$

풀이

$i$번 정점과 $j$번 정점 사이의 인접 연결 정보를 저장한 행렬을 $A$,
$i$번 정점과 $j$번 정점 사이 거리가 2인 연결 정보를 저장한 행렬을 $B$라 하면
$A^2 = B$인지 아닌지를 확인하면 된다.
그러나 일반적인 행렬 제곱 시 $O(N^3)$이므로 시간 제한에 걸리게 된다.

 

$Freivalds' \space algorithm$이라는 신박한 알고리즘이 존재한다.
$x \in \mathbb{R}^n$라 할 때, $A^2 x = Bx$인 경우 약 $\frac{1}{2}$의 확률로 $A^2=B$이다.
이 곱셈의 시간복잡도는 $O(N^2)$이다.
random한 $x$에 대해 10번 확인 시 적중 확률은 99.9%이다.

코드

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

int N, a[1005][1005], b[1005][1005];  
long long x[1005], ax[1005], aax[1005], bx[1005];  

struct Random {  
    mt19937 rd;  
    Random() : rd((unsigned)chrono::steady_clock::now().time_since_epoch().count()) {}  
    int GetInt(int l = 0, int r = 32767) {  
        return uniform_int_distribution<int>(l, r)(rd);  
    }    double GetDouble(double l = 0, double r = 1) {  
        return uniform_real_distribution<double>(l, r)(rd);  
    }} Rand;  

int main()  
{  
    cin.tie(0)->sync_with_stdio(0);  
    while (1)  
    {        cin>>N; if (!N) return 0;  
        for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++)
            cin>>a[i][j];  
        for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++)
            cin>>b[i][j];  
        bool ok = true;  
        for (int K = 1; K <= 10 && ok; K++) {  
            for (int i = 1; i <= N; i++) x[i] = Rand.GetInt();  
            for (int i = 1; i <= N; i++) {  
                ax[i] = 0;  
                for (int j = 1; j <= N; j++)
                    ax[i] += x[j] * a[i][j];  
            }            
            for (int i = 1; i <= N; i++) {  
                aax[i] = 0;  
                for (int j = 1; j <= N; j++)
                    aax[i] += ax[j] * a[i][j];  
            }            
            for (int i = 1; i <= N; i++) {  
                bx[i] = 0;  
                for (int j = 1; j <= N; j++)
                    bx[i] += x[j] * b[i][j];  
                if (aax[i] != bx[i]) {ok = false; break;}  
            }        
        }        
        cout<<(ok ? "YES\n" : "NO\n");  
    }
}