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..
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..
차수가 n인 다항식 f(x)=c0+c1x1+c2x2+⋯+cnxn(cn≠0)가 있다. 그리고 차수 m인 다항식 g(x)=d0+d1x1+d2x2+⋯+dmxm(dm≠0)이 있다. 이를 다항식 q와 r을 이용하여, f(x)=g(x)q(x)+r(x)라고 나타내 보자. r(x)의 차수가 m보다 작은 경우, f를 g로 나눈 몫을 q, 나머지를 r이라고 정의한다. 다항식 q의 차수는 n−m이다. 다항식의 나눗셈을 교과과정에서 배운대로 구현한다면 O(nm) 시간복잡도가 된다. 이를 좀 더 빠르게 하는 방법에 대해서 알아보자. Rev(f)를..
- Total
- Today
- Yesterday
- idea
- Dynamic Pramming
- IOI2012
- Divide & Conquer
- USACO
- BOI
- Boyer
- HackerRank
- majority
- Algorithm
- IOI2014
- Segment tree
- moore
- TRIE
- Boyer-Moore Majority Vote Algorithm
- Knuth Optimization
- Greedy Method
- dynamic programming
- z-trening
- optimization
- BOI 2001
- IOI2013
- Parametric Search
- Dijkstra
- ioi
- Tree
- vote
- Splay Tree
- IOI2011
- BOI 2009
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |