Bostan Mori 알고리즘
Bostan Mori 알고리즘은 2020년 8월 Alin Bostan과 Ryuhei Mori가 작성한 이 논문에 소개되어 있는 선형점화식을 가지는 수열의 N 번째 항을 빠르게 구하는 알고리즘이다. Bostan Mori 알고리즘 이외에 선형점화식을 가지는 수열의 N 번째 항을 빠르게 구하는 방법은 이 글을 참고하자. D0,D1,⋯,Dk−1과 c1,c2,⋯,ck가 주어졌을 때, i≥k인 Di를 다음과 같은 선형점화식으로 구할 수 있다고 하자. Di=k∑j=1cjDi−j=c1Di−1+c2Di−2+⋯+ckDi−k 이러한 선형점화식이 주어졌을 때, DN..
공부
2022. 11. 30. 15:53
선형점화식 빠르게 계산하기
D0,D1,⋯,Dk−1과 c1,c2,⋯,ck가 주어졌을 때, i≥k인 Di를 다음과 같은 선형점화식으로 구할 수 있다고 하자. Di=k∑j=1cjDi−j=c1Di−1+c2Di−2+⋯+ckDi−k 이러한 선형점화식을 가지는 가장 유명한 예시는 피보나치 수열이다. 피보나치 수열은 위 식에서 k=2, D0=1, D1=1, c1=1, c2=2이다. 이러한 선형점화식이 주어졌을 때, DN을 빠르게 구하는 방법을 알아보자. 1) 행렬 곱셈을 이용한 방법 $$\begin{pmatrix} D_N \\ D_{N-1}\\ D_{N..
공부
2022. 11. 30. 10:14
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- ioi
- IOI2014
- Dynamic Pramming
- z-trening
- majority
- Tree
- vote
- BOI
- Dijkstra
- TRIE
- optimization
- Parametric Search
- BOI 2001
- IOI2013
- Boyer
- Segment tree
- Boyer-Moore Majority Vote Algorithm
- Divide & Conquer
- HackerRank
- USACO
- BOI 2009
- Greedy Method
- Splay Tree
- Knuth Optimization
- dynamic programming
- IOI2011
- IOI2012
- moore
- idea
- Algorithm
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함