DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

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)