N Seeds

Let $S_k=a_1+a_2+\cdots+a_k$. The recurrence can be rewritten as

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

There are at most four unknowns: $a_2,a_3,\cdots,a_P$. Moreover,

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

Therefore, if $U=\lfloor\sqrt[P]{X}\rfloor$, then $S_P\leq U$, which bounds all seed values.

Fix $n=P+1,P+2,\cdots,10$ in turn. Enumerate $a_2,a_3,\cdots,a_{P-1}$. Use the sum of the chosen values and the minimum possible remaining values to discard candidates that cannot satisfy .

Once these values are fixed, increasing $a_P$ never decreases any prefix sum or later sequence term. Thus, binary search $a_P$ between $1$ and $U-S_{}$. While evaluating the recurrence, cap every value above at to avoid overflow.

There are at most five possible values of $n$. The time complexity is $O(U^{P-2}\log U)$, where $U\leq\lfloor\sqrt[P]{2\times10^9}\rfloor$. The space complexity is .

Solution written by GPT6