N Seeds

$S_k=a_1+a_2+\cdots+a_k$라 하자. 점화식은 다음과 같이 정리할 수 있다.

$$a_n=S_{n-1}^{P}+S_{n-2}^{P-1}+\cdots+S_{n-P}$$

미지수는 $a_2,a_3,\cdots,a_P$로 최대 개이다. 또한

$$X=a_n\geq S_P^P$$

이므로 $U=\lfloor\sqrt[P]{X}\rfloor$라 하면 $S_P\leq U$이다. 따라서 가능한 시드 값의 범위가 제한된다.

$n=P+1,P+2,\cdots,10$을 차례로 고정한다. $a_2,a_3,\cdots,a_{P-1}$을 완전 탐색한다. 이때 이미 정한 값의 합과 남은 항의 최솟값을 이용하여 를 만족할 수 없는 후보는 제외한다.

나머지 값을 고정하면 $a_P$가 증가할 때 모든 접두합과 이후의 항은 감소하지 않는다. 따라서 $a_P$는 $1$ 이상 $U-S_{P-1}$ 이하에서 이분 탐색할 수 있다. 계산 중 값이 를 넘으면 로 잘라 오버플로를 방지한다.

가능한 $n$은 최대 $5$개이다. 시간 복잡도는 $O(U^{P-2}\log U)$이고, $U\le \lfloor \sqrt[P]{2\times {10}^9}\rfloor$이다. 공간 복잡도는 이다.

Solution written by GPT6