일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 기하
- acmicpc.net
- 세그먼트 트리
- Manacher's algorithm
- 백준 온라인 저지
- BAPC 2018
- Implementation
- Manacher 알고리즘
- BAPC
- POI Solution
- 8192
- ICPC 연습
- Divide and conquer optimization
- 볼록 껍질
- 그래프
- Z algorithm
- boj
- codeforces
- JOI
- 컨벡스 헐
- DP
- 2794
- 코드포스
- 14179
- JOI 2018
- convex hull
- 구현
- IOI 2013
- Z 알고리즘
- 기하 알고리즘
- Today
- Total
프로그래밍 연습장
키타마사 법 본문
재귀적 수열은 어떤 $k$에 대해 $n>k$라면 $a_n = \sum _{i=1}^k w_i a_{n-i}$가 성립하는 수열을 뜻한다. 가장 간단한 재귀적 수열은 피보나치 수열로, $k=2$, $w = [1, 1]$인 수열이다.
행렬의 제곱을 이용해 재귀적 수열의 $n$번째 항을 빠르게 구할 수 있다. $a_n$을 그 전 $k$개 항의 선형 결합으로 나타내어 보면, 매 항에 대해서 선형 결합의 형태가 같음을 확인할 수 있다. 따라서 같은 행렬을 $n$여 번 곱하는 형태로 $a_n$에 대한 식을 구할 수 있으며, 이는 단순한 알고리즘으로 $O(k^3 \log n)$의 시간 복잡도로 문제를 해결할 수 있게 한다.
더 빠른 방법이 있다: 키타마사 법(Kitamasa method, きたまさ法)로 불리는 방법으로 시간 복잡도인 $O(k^2 \log n)$에 임의의 항을 구할 수 있다. 피보나치 같이 $k=2$ 정도로 작으면 무관하지만, 거대한 귀납적 수열에서는 성능을 크게 향상시킬 수 있다.
키타마사 법의 핵심 아이디어는, 수열의 원소 $a_n$은 항상 어떠한 형태로 $a_{1..k}$의 정수 배의 합으로 나타내어진다는 것이다:
$c_{1..k}$가 존재해, $a_n = \sum_{i=1}^k a_i c_i$
따라서, 다음이 성립한다.
$$a_{2n} = \sum_{i=1}^k a_{n+i} c_i = \sum_{i=1}^k \sum_{j=1}^k a_{i+j} c_i c_j$$
그리고,
$$a_{n+1} = \sum_{i=1}^k a_{i+1} c_i = w_k c_k a_1 + \sum_{i=2}^k (c_{i-1} + w_{k+1-i} c_k ) a_i $$
또한 성립한다. 따라서, $a_n$의 $c_{1..k}$ 표현을 알고 있으면 $O(k^2)$에 $a_{2n}$의 $c_{1..k}$ 표현을, $O(k)$에 $a_{n+1}$의 $c_{1..k}$ 표현을 얻을 수 있다. $a_1$은 $c_{1..k} = [1, 0, \cdots , 0]$을 가지므로, 총 $O(k^2 \log n)$에 $a_n$의 $c_{1..k}$ 표현을 구할 수 있고, 이로부터 빠르게 $a_n$의 값을 알 수 있다.
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 41 42 43 44 45 46 47 48 | #include <bits/stdc++.h> using namespace std; typedef long long lint; const int mod = 1000000007; int k, a[1004], w[1004]; int add(int x, int y) { return (x+y) % mod; } int mul(int x, int y) { return (x*(lint)y) % mod; } int kitamasa(lint n) { vector<int> c(k+1, 0); c[1] = 1; // n = 1 만들기 int b = 62; while ((n>>b)%2==0) b--; for (b--; ~b; b--) { // c(n) -> c(2n) vector<int> d(2*k+1, 0); for (int i=1; i<=k; i++) for (int j=1; j<=k; j++) d[i+j] = add(d[i+j], mul(c[i], c[j])); for (int i=2*k; i>k; i--) for (int j=1; j<=k; j++) d[i-j] = add(d[i-j], mul(d[i], w[j])); d.resize(k+1); c = d; // c(n) -> c(n+1) if ((n>>b)&1) { vector<int> d(k+1, 0); d[1] = mul(c[k], w[k]); for (int i=2; i<=k; i++) d[i] = c[i-1] + mul(c[k], w[k+1-i]); c = d; } } int ans = 0; for (int i=1; i<=k; i++) ans = add(ans, mul(a[i], c[i])); return ans; } int main() { lint n; cin >> n >> k; for (int i=1; i<=k; i++) cin >> a[i]; // 첫 k개의 항 for (int i=1; i<=k; i++) cin >> w[i]; // 점화식의 계수 cout << kitamasa(n); } | cs |
참조: #
고속 푸리에 변환을 응용한 방법으로 전이 과정을 $O(k \log k)$에 수행할 수도 있다. 이를 고속 키타마사법이라고 따로 이름 붙이기도 하나 보다. 이로서 같은 문제를 $O(k \log k \log n)$의 시간에 해결할 수도 있다. #
'알고리즘' 카테고리의 다른 글
Ray Casting Algorithm (5) | 2019.07.21 |
---|---|
Skip List (2) | 2018.03.31 |
Manacher의 알고리즘과 Z 알고리즘 (0) | 2018.02.27 |
그래프의 간선 리스트 표현 (2) | 2017.12.06 |
Heavy Light Decomposition의 구현 (0) | 2017.12.03 |