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

개요

문제 링크
다이아 5, 선형대수학, 무작위화
A×B=C를 만족하는 겹치지 않는 부분행렬의 최대개수

---

접근

1. Freivald's algorithm을 사용하는 세 문제 중 두 번째. 다이아 하위 문제는 보통 새로운 어려운 알고리즘을 사용하는 문제가 많은 것 같다. 그래봐야 전체 2700개 다이아 문제 중 7개 풀었지만 내 좁은 시야에서는 암튼 그렇다.
2. 문제로 돌아오자. 우선 정수범위가 터질 수 있으니 long long을 사용하고, N이 256이고, L이 4000에서 100만정도 되므로 시간을 잘 관리해야 한다. O(N^3)에 하면 무조건 터지므로 O(kN^2)에 A×B=C를 유사하게 검증할 수 있는 프리발즈 알고리즘을 사용한다.
3. 다음으로 0부터 L까지 돌면서 개수를 세어주면 되는데, 앞에서부터 그냥 세어주면 된다. 왜냐?
   1. 만약 [i,i+3×N]사이의 j에 대해서 [j,j+3×N]이 조건을 만족한다고 생각하면, j를 선택하는 것은 손해이다.
   2. 왜냐하면 [i+3×N,j+3×N] 사이의 조건을 만족하는 k를 놓칠 수 있기 때문이다.
   3. 그래서 이 문제가 그리디 문제가 된다. 그리디한 인간은 앞에서부터 하나씩 찾아가기 때문이다.
4. 나머지는 입력 최적화해주고, 크게 복잡할 것은 없다.

---

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)

---

Source code

#include <iostream>
#include <cstdlib>
#include <ctime>
#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;
}