9461번 - 파도반 수열
그림으로부터 점화관계 $P(n)=P(n-1)+P(n-5)$ $(\text{단, } P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2)$ 를 얻어 낼 수 있습니다.
수학적 귀납법으로 $P(n)=P(n-2)+P(n-3)$을 증명해봅시다.
$(1)$ $n \le 5$일 때초항에 의해 성립합니다.
$(2)$ $k$ 이하의 $n$에서 성립함을 가정하면
$n = k+1$에서
\[\begin{aligned}P(k+1) &= P(k) + P(k-4) \\ &= P(k-1) + P(k-5) + P(k-4) \\ &= P(k-1) + P(k-2) \quad \text{($n = k-2$에서 성립함을 이용)}\end{aligned}\]
따라서 3 이상의 모든 n에 대해 $P(n)=P(n-2)+P(n-3)$ $(\text{단, } P(1)=P(2)=P(3)=1)$이 성립합니다.
이제 이 점화식의 일반해를 구합시다.
특성방정식은 $x^{3}-x-1=0$입니다.
카르다노의 공식으로 세 특성근을 구하면 다음과 같습니다.
\[\begin{cases}x = \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},\\[2mm]x = \omega \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \omega^2 \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},\\[1mm]x = \omega^2 \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \omega \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}}, \end{cases}\]
여기서 $\omega = \dfrac{-1+\sqrt{3}i}{2}$입니다.
세 근을 순서대로 $a, b, c$라고 둡시다. ($a$가 실근입니다)
$P(n) = A a^n + B b^n + C c^n$가 됩니다.
$n$에 $1, 2, 3$을 대입하면
\[\begin{cases}A a + B b + C c = 1,\\A a^2 + B b^2 + C c^2 = 1,\\A a^3 + B b^3 + C c^3 = 1\end{cases}\]
크래머 공식으로 이걸 풀면
\[\begin{cases}A &= \frac{(1-b)(1-c)}{a(a-b)(a-c)}, \\B &= \frac{(1-c)(1-a)}{b(b-c)(b-a)}, \\C &= \frac{(1-a)(1-b)}{c(c-a)(c-b)}\end{cases}\]
이걸 대입하면
\[P(n) = \displaystyle\sum_{\text{cyc}} \frac{a^{\,n-1} (1-b)(1-c)}{(a-b)(a-c)}\]
$a, b, c$에 세 근을 대입하면
\[\begin{aligned}P(n) &= \dfrac{\left( 1 - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( 1 - \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}}{\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right) \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}- \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)} \\[1mm]&+\dfrac{\left( 1 - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( 1 - \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}}{\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} - \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} - \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)} \\[1mm]&+\dfrac{\left( 1 - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( 1 - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}}{\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}- \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}- \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} - \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)}\end{aligned}\]
와 같이 됩니다.
이제 여기에 $n$을 대입하면 됩니다.
실수 오차가 생기므로 허수부분을 없애고 실수부분에 round를 하면 됩니다.
참고로 저는 이렇게 푸느니 DP로 풀었습니다.
행렬을 이용해보는것도 좋을것 같습니다
https://www.acmicpc.net/proble...
피보나치는 외우고 있습니다만
$\dfrac{1}{\sqrt{5}}\Bigl(\Bigl(\dfrac{1+\sqrt{5}}{2}\Bigr)^{n}-\Bigl(\dfrac{1-\sqrt{5}}{2}\Bigr)^{n}\Bigr)$
일반항을 이용하면 분할정복을 이용해 O(log n)으로 풀수있지만 계산이 복잡하므로 행렬을 이용하면 똑같은 시간복잡도로 풀수있습니다 공부해보시면 도움이 되실것같아서 링크는 연습문제로 남긴것입니다
저는 삼차방정식 문제 근의공식으로 푼 사람입니다 ㅋㅋㅋ
수식 오류 좀 고쳤습니다
댓글을 작성하려면 로그인해야 합니다.
erick12 1년 전 11
그림으로부터 점화관계 $P(n)=P(n-1)+P(n-5)$ $(\text{단, } P(1) = 1, P(2) = 1, P(3) = 1, P(4) = 2, P(5) = 2)$ 를 얻어 낼 수 있습니다.
수학적 귀납법으로 $P(n)=P(n-2)+P(n-3)$을 증명해봅시다.
$(1)$ $n \le 5$일 때
초항에 의해 성립합니다.
$(2)$ $k$ 이하의 $n$에서 성립함을 가정하면
$n = k+1$에서
\[
\begin{aligned}
P(k+1) &= P(k) + P(k-4) \\
&= P(k-1) + P(k-5) + P(k-4) \\
&= P(k-1) + P(k-2) \quad \text{($n = k-2$에서 성립함을 이용)}
\end{aligned}
\]
따라서 3 이상의 모든 n에 대해 $P(n)=P(n-2)+P(n-3)$ $(\text{단, } P(1)=P(2)=P(3)=1)$이 성립합니다.
이제 이 점화식의 일반해를 구합시다.
특성방정식은 $x^{3}-x-1=0$입니다.
카르다노의 공식으로 세 특성근을 구하면 다음과 같습니다.
\[
\begin{cases}
x = \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},\\[2mm]
x = \omega \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \omega^2 \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},\\[1mm]
x = \omega^2 \sqrt[3]{\dfrac{1}{2} + \sqrt{\dfrac{23}{108}}} \;+\; \omega \sqrt[3]{\dfrac{1}{2} - \sqrt{\dfrac{23}{108}}},
\end{cases}
\]
여기서 $\omega = \dfrac{-1+\sqrt{3}i}{2}$입니다.
세 근을 순서대로 $a, b, c$라고 둡시다. ($a$가 실근입니다)
$P(n) = A a^n + B b^n + C c^n$가 됩니다.
$n$에 $1, 2, 3$을 대입하면
\[
\begin{cases}
A a + B b + C c = 1,\\
A a^2 + B b^2 + C c^2 = 1,\\
A a^3 + B b^3 + C c^3 = 1
\end{cases}
\]
크래머 공식으로 이걸 풀면
\[
\begin{cases}
A &= \frac{(1-b)(1-c)}{a(a-b)(a-c)}, \\
B &= \frac{(1-c)(1-a)}{b(b-c)(b-a)}, \\
C &= \frac{(1-a)(1-b)}{c(c-a)(c-b)}
\end{cases}
\]
이걸 대입하면
\[
P(n) = \displaystyle\sum_{\text{cyc}} \frac{a^{\,n-1} (1-b)(1-c)}{(a-b)(a-c)}
\]
$a, b, c$에 세 근을 대입하면
\[
\begin{aligned}
P(n) &=
\dfrac{
\left( 1 - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( 1 - \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}
}{
\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
} \\[1mm]
&+
\dfrac{
\left( 1 - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( 1 - \left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}
}{
\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} - \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)
} \\[1mm]
&+
\dfrac{
\left( 1 - \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( 1 - \left( \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)^{n-1}
}{
\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \left( \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right) \right)
\left( \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} + \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}}
- \dfrac{-1+\sqrt{3}i}{2} \sqrt[3]{\dfrac12 + \sqrt{\dfrac{23}{108}}} - \dfrac{-1-\sqrt{3}i}{2} \sqrt[3]{\dfrac12 - \sqrt{\dfrac{23}{108}}} \right)
}
\end{aligned}
\]
와 같이 됩니다.
이제 여기에 $n$을 대입하면 됩니다.
실수 오차가 생기므로 허수부분을 없애고 실수부분에 round를 하면 됩니다.