사용자 도구

사이트 도구


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)에 계산해주면 끝.

코드

(다이아몬드 이상은 코드 생략)

토론

댓글을 입력하세요:
S X V N U
 
ps/problems/boj/19102.txt · 마지막으로 수정됨: 2023/08/20 16:10 저자 teferi