DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

N Seeds

Back to problem

Editorial

Let Sk=a1+a2+⋯+akS_k=a_1+a_2+\cdots+a_kSk​=a1​+a2​+⋯+ak​. The recurrence can be rewritten as

an=Sn−1P+Sn−2P−1+⋯+Sn−P.a_n=S_{n-1}^{P}+S_{n-2}^{P-1}+\cdots+S_{n-P}.an​=Sn−1P​

There are at most four unknowns: a2,a3,⋯ ,aPa_2,a_3,\cdots,a_Pa2​,a3​,⋯,aP​. Moreover,

X=an≥SPP.X=a_n\geq S_P^P.X=an​≥SPP​.

Therefore, if U=⌊XP⌋U=\lfloor\sqrt[P]{X}\rfloorU=⌊PX​⌋, then SP≤US_P\leq U, which bounds all seed values.

Fix n=P+1,P+2,⋯ ,10n=P+1,P+2,\cdots,10n=P+1,P+2,⋯,10 in turn. Enumerate a2,a3,⋯ ,aP−1a_2,a_3,\cdots,a_{P-1}a. 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 aPa_PaP​ never decreases any prefix sum or later sequence term. Thus, binary search aPa_PaP​ between 111 and U−S. While evaluating the recurrence, cap every value above at to avoid overflow.

There are at most five possible values of nnn. The time complexity is O(UP−2log⁡U)O(U^{P-2}\log U)O(UP−2logU), where U≤⌊2×109P⌋U\leq\lfloor\sqrt[P]{2\times10^9}\rfloorU≤. The space complexity is .

Solution written by GPT6

+
Sn−2P−1​+
⋯+
Sn−P​.
SP​≤
U
2​
,
a3​
,
⋯
,
aP−1​
SP≤US_P\leq USP​≤U
P−1U-S_{P-1}
U−SP−1​
XXX
X+1X+1X+1
⌊P2×109​⌋
O(1)O(1)O(1)