키타마사법 – 학습

1강 선형 점화식의 N번째 항을 빠르게 공식

문제

차수 $$k$$ 의 선형 점화식

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$

이 주어졌을 때 $$a_N$$ ( $$N$$ 이 $10^{18}$ 급)을 구한다. 행렬 거듭제곱이 $O(k^3\log N)$ 인데, 키타마사법은 이를 $O(k^2\log N)$ (다항식 곱셈을 FFT로 하면 $O(k\log k\log N)$ )으로 낮춘다.

핵심 통찰: 다항식 잉여

수열의 한 항은 초기항들의 선형결합으로 표현된다. $$x^n$$ 을 점화식의 특성다항식

$f(x) = x^k - c_1 x^{k-1} - c_2 x^{k-2} - \cdots - c_k$

으로 나눈 나머지

$x^n \equiv \sum_{i=0}^{k-1} r_i x^i \pmod{f(x)}$

를 구하면,

$a_n = \sum_{i=0}^{k-1} r_i\, a_i$

가 된다. 왜냐하면 $x^k \equiv c_1 x^{k-1}+\cdots+c_k \pmod f$ 라는 관계가 정확히 점화식과 동형이기 때문이다. $$x$$ 에 "한 칸 시프트" 연산을 대입하면 다항식 환 $\mathbb{F}[x]/(f)$ 에서의 계산이 수열 항 계산과 일치한다.

$x^N \bmod f$ 를 빠르게

$x^N \bmod f$ 는 다항식 환에서의 거듭제곱이다. 이진 거듭제곱으로

$x^N = (x^{N/2})^2 \cdot x^{N \bmod 2}$

를 따라가며, 매 단계 곱한 뒤 $$f$$ 로 나눈 나머지(차수 $$)만 유지한다. 곱셈은 차수 \( 두 다항식의 곱이라 결과 차수 \(<2k$, 이를 $f$ 로 나눠 다시 차수 \( 로 줄인다.$

복잡도

곱/나눗셈 방식	한 단계	전체
단순 ( $$O(k^2)$$ )	$$O(k^2)$$	$O(k^2\log N)$
FFT/NTT	$O(k\log k)$	$O(k\log k\log N)$

행렬 거듭제곱과의 관계

행렬 거듭제곱의 동반행렬(companion matrix)이 곧 $\mathbb{F}[x]/(f)$ 에서의 곱 $$x$$ 에 해당한다. 키타마사는 그 행렬을 명시하지 않고 다항식 산술로 같은 결과를 더 싸게 얻는다.

2강 키타마사법 구현과 활용 공식

구현 ( $O(k^2\log N)$ 버전)

점화식 계수 rec[0..k-1] ( $a_n=\sum rec[i]\,a_{n-1-i}$ ) 와 초기항 init[0..k-1] 로 $$a_N$$ 을 구한다. 모듈러 환경.

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

vector<ll> rec, init_terms;       // rec[i]: a_n = sum rec[i]*a_{n-1-i}, i=0..k-1

// 차수 < k 다항식 두 개를 곱한 뒤 특성다항식으로 reduce
vector<ll> mul_mod(const vector<ll>& a, const vector<ll>& b) {
    int k = rec.size();
    vector<ll> c(a.size() + b.size() - 1, 0);
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = 0; j < (int)b.size(); j++)
            c[i + j] = (c[i + j] + a[i] * b[j]) % MOD;
    // x^k = sum rec[i] x^{k-1-i} 를 이용해 차수를 내린다
    for (int i = (int)c.size() - 1; i >= k; i--) {
        for (int j = 0; j < k; j++)
            c[i - 1 - j] = (c[i - 1 - j] + c[i] * rec[j]) % MOD;
        c[i] = 0;
    }
    c.resize(k);
    return c;
}

ll kitamasa(ll N) {
    int k = rec.size();
    if (N < k) return init_terms[N];
    vector<ll> result = {1};        // = x^0
    vector<ll> base = {0, 1};       // = x
    if (k == 1) base = mul_mod(base, base), base.resize(1); // 안전 처리
    while (N) {
        if (N & 1) result = mul_mod(result, base);
        base = mul_mod(base, base);
        N >>= 1;
    }
    ll ans = 0;                     // a_N = sum result[i] * init[i]
    for (int i = 0; i < k; i++)
        ans = (ans + result[i] * init_terms[i]) % MOD;
    return ans;
}

자주 하는 실수

점화식 부호. 특성다항식 $f(x)=x^k - \sum c_i x^{k-1-...}$ 에서 reduce할 때 부호를 빠뜨리기 쉽다. x^k = sum rec[j] x^{k-1-j} 형태를 코드와 일치시킨다.
$\(N 처리.$ 초기항을 그대로 반환해야 한다.
차수 관리. 곱 결과를 reduce 후 반드시 resize(k).
모듈러 음수. 점화식 계수가 음수면 (rec[j]%MOD+MOD)%MOD 로 정규화.

응용

상황	효과
큰 $$N$$ 의 피보나치/일반 선형점화	$O(k^2\log N)$
벌리캠프-매시로 구한 점화식의 먼 항	BM + 키타마사 콤보
그래프 경로 수(고정 길이)	인접행렬 점화 → 다항식화

FFT 결합

$$k$$ 가 크면 mul_mod 의 곱셈을 NTT로, reduce를 다항식 나눗셈(역원 기반)으로 바꿔 $O(k\log k\log N)$ 을 얻는다. 벌리캠프-매시로 미지의 점화식을 복원한 뒤 키타마사로 임의 항을 뽑는 조합이 경시에서 강력하다.