DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

N Seeds

返回题目

题解

Sk=a1+a2+⋯+akS_k=a_1+a_2+\cdots+a_kSk​=a1​+a2​+⋯+ak​라 하자. 점화식은 다음과 같이 정리할 수 있다.

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

미지수는 a2,a3,⋯ ,aPa_2,a_3,\cdots,a_Pa2​,a3​,⋯,aP​로 최대 개이다. 또한

X=an≥SPPX=a_n\geq S_P^PX=an​≥SPP​

이므로 U=⌊XP⌋U=\lfloor\sqrt[P]{X}\rfloorU=⌊PX​⌋라 하면 SP≤US_P\leq U이다. 따라서 가능한 시드 값의 범위가 제한된다.

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

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

가능한 nnn은 최대 555개이다. 시간 복잡도는 O(UP−2log⁡U)O(U^{P-2}\log U)O(UP−2logU)이고, U≤⌊2×109P⌋이다. 공간 복잡도는 이다.

Solution written by GPT6

+
Sn−2P−1​+
⋯+
Sn−P​
44
4
SP​≤
U
2​
,
a3​
,
⋯
,
aP−1​
SP≤US_P\leq USP​≤U
U−SP−1​
XXX
X+1X+1X+1
U\leq\lfloor\sqrt[P]{2\times10^9}\rfloor
U≤⌊P2×109​⌋
O(1)O(1)O(1)