벌리캠프-매시 – 학습

1강 수열에서 최소 선형 점화식 찾기 공식

문제

수열 $a_0, a_1, \dots, a_{2k-1}$ 의 앞부분이 주어졌을 때, 이를 생성하는 최소 차수의 선형 점화식

$a_n = \sum_{i=1}^{L} c_i\, a_{n-i}$

을 찾는다. 벌리캠프-매시(BM) 알고리즘은 이를 $$O(n^2)$$ (필드 $\mathbb{F}_p$ 위)에 구한다. 원래 LFSR(선형 되먹임 시프트 레지스터)의 최단 길이를 찾는 부호이론 알고리즘이지만, 경시에서는 "수열을 보고 점화식 역설계 → 키타마사로 먼 항" 콤보로 쓰인다.

점진적 갱신

앞에서부터 한 항씩 보며 현재 추정 점화식 $$C$$ 를 유지한다. 항 $$a_i$$ 에 대해 현재 점화식이 예측한 값과 실제 값의 차이를 discrepancy

$\delta = a_i - \sum_{j=1}^{L} c_j\, a_{i-j}$

라 하자. $\delta = 0$ 이면 현재 점화식이 이 항도 맞춘 것이라 그대로 둔다. $\delta \ne 0$ 이면 점화식을 보정해야 한다.

보정 규칙

가장 최근에 길이를 늘렸던 시점의 점화식 $$B$$ 와 그때의 discrepancy $\delta_B$ 를 기억해 둔다. 보정은

$C \leftarrow C - \frac{\delta}{\delta_B}\, x^{\,(i - m)}\, B$

형태로, $$B$$ 를 적절히 시프트·스케일해 빼서 현재 항의 오차를 정확히 상쇄한다( $$m$$ = $$B$$ 를 마지막으로 저장한 인덱스). 이때 점화식 길이가 늘어나야 하면 ( $2L \le i$ ) 길이를 $L \leftarrow i+1-L$ 로 갱신하고 현재 $C,\delta$ 를 새로운 $B,\delta_B$ 로 저장한다.

최소성과 정확성

BM이 출력하는 점화식은 주어진 항들을 모두 만족하는 최단 LFSR임이 보장된다(Berlekamp–Massey 정리). 길이 갱신 조건 $2L \le i$ 가 최소성을 강제한다. 입력이 길이 $\ge 2L$ 이면 진짜 점화식을 정확히 복원한다. 따라서 안전하게 쓰려면 항을 점화식 차수의 두 배 이상 주어야 한다.

복잡도

단계	비용
항당 discrepancy + 보정	$$O(L)$$
전체	$O(nL) \le O(n^2)$

2강 BM 구현과 키타마사 결합 공식

표준 구현 (모듈러 필드)

입력 수열 s 로부터 점화식 계수 C ( $a_n=\sum C[i]\,a_{n-1-i}$ ) 를 반환한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

ll power(ll a, ll b){ ll r=1; a%=MOD; for(;b;b>>=1,a=a*a%MOD) if(b&1) r=r*a%MOD; return r; }

vector<ll> berlekamp_massey(const vector<ll>& s) {
    vector<ll> C, B;            // 현재 점화식, 마지막 길이변경 시점 점화식
    C = {1}; B = {1};           // 다항식 1 - c1 x - c2 x^2 ... 의 계수(부호 포함)
    int L = 0, m = 1;
    ll b = 1;                   // 마지막 nonzero discrepancy
    for (int i = 0; i < (int)s.size(); i++) {
        ll delta = s[i] % MOD;
        for (int j = 1; j <= L; j++)
            delta = (delta + C[j] * s[i - j]) % MOD;
        if (delta == 0) { m++; continue; }
        if (2 * L <= i) {                          // 길이 증가
            vector<ll> T = C;
            ll coef = delta * power(b, MOD - 2) % MOD;
            C.resize(max(C.size(), B.size() + m));
            for (int j = 0; j < (int)B.size(); j++)
                C[j + m] = (C[j + m] - coef * B[j]) % MOD;
            L = i + 1 - L; B = T; b = delta; m = 1;
        } else {                                   // 길이 유지, 보정만
            ll coef = delta * power(b, MOD - 2) % MOD;
            C.resize(max(C.size(), B.size() + m));
            for (int j = 0; j < (int)B.size(); j++)
                C[j + m] = (C[j + m] - coef * B[j]) % MOD;
            m++;
        }
    }
    // C = {1, -c1, -c2, ...} 이므로 점화식 계수로 변환
    vector<ll> rec(L);
    for (int i = 1; i <= L; i++) rec[i - 1] = (MOD - C[i] % MOD) % MOD;
    return rec;                  // a_n = sum rec[i] * a_{n-1-i}
}

자주 하는 실수

부호 변환. 내부 다항식 $$C$$ 는 $1 - c_1 x - \cdots$ 꼴. 점화식 계수로 바꿀 때 부호를 뒤집는다.
입력 길이 부족. 진짜 차수 $$L$$ 인데 항을 $$2L$$ 미만 주면 잘못된(짧은) 점화식이 나온다.
모듈러 역원. $$b$$ 의 역원을 페르마로 구하므로 $$MOD$$ 가 소수여야 한다.
$$m$$ 관리. discrepancy가 0일 때도 $$m$$ 을 증가시켜야 시프트가 맞는다.

키타마사와의 콤보

BM으로 점화식을 복원했으면, 임의의 먼 항 $$a_N$$ 은 키타마사법으로 $O(L^2\log N)$ 에 구한다.

// rec = berlekamp_massey(samples);  init = 처음 L개 항;
// a_N = kitamasa(N);  (키타마사 단원의 함수 재사용)

응용

상황	흐름
미지의 선형점화 수열의 $$N$$ 번째 항	BM → 키타마사
그래프 경로 수/행렬 거듭제곱 추측	처음 몇 항 brute → BM
조합 점화식 검증	BM이 짧은 점화식 찾으면 단순화 가능

주의

BM은 입력이 정말 선형 점화를 따른다는 보장이 없으면 위험하다. 복원 후 추가 항으로 교차 검증(예측 vs 실제)하는 습관을 들이면 오답을 거른다.

단계	비용
항당 discrepancy + 보정	$\(O(L)\)$
전체	$O(nL) \le O(n^2)$

상황	흐름
미지의 선형점화 수열의 $\(N\)$ 번째 항	BM → 키타마사
그래프 경로 수/행렬 거듭제곱 추측	처음 몇 항 brute → BM
조합 점화식 검증	BM이 짧은 점화식 찾으면 단순화 가능