ps:problems:boj:19102
목차
Array Challenge
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 19102 |
| 문제명 | Array Challenge |
| 레벨 | 다이아몬드 5 |
| 분류 |
벌리캠프-매시 |
| 시간복잡도 | O(T*logn) |
| 인풋사이즈 | T<=1000, n<=10^15 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 31256KB / 280ms |
| 최고기록 | 280ms |
| 해결날짜 | 2023/08/20 |
풀이
- 정신 나갈것 같은 문제. 감도 안잡히는 복잡한 점화식이 주어진다..
- 태그를 까보면 벌리캠프-매시를 돌려야 한다는 것을 알수 있긴 하지만, 태그없이는 대체 제곱근에 floor까지 붙은 형태의 함수가 선형 점화식 꼴로 표현될수 있을거라는 상상을 어떻게 할수 있을지..
- 아무튼 벌리캠프-매시를 돌려보면 정말 충격적이게도 이 복잡한 형태의 점화식이 인접 3항간의 선형점화식으로 표현된다. 너무 간단해서 어이가 없을지경..
- 실제 제출 코드에는 이렇게 구한 점화식의 계수를 그냥 적어놓고, 입력으로 들어오는 n에 대해 n번째 항의 값을 O(logn)에 계산해주면 끝.
코드
(다이아몬드 이상은 코드 생략)
- Dependency: teflib.combinatorics.linear_recurrence
ps/problems/boj/19102.txt · 마지막으로 수정됨: 2023/08/20 16:10 저자 teferi
토론