考察
最後のsplit位置をjとすると、prefix X[1,j]の全分割積へ最後の整数X[j+1,i]を掛けるので、dp_i=Σ_{j=0}^{i-1}dp_j·X[j+1,i]となる。substring整数は末尾digit d_iを付けるとX[j+1,i]=10X[j+1,i-1]+d_iになり、二次和を前段DPとprefix sumへまとめられる。10dp_{i-1}は、以前の全最後blockを1桁左shiftした寄与の総和に一致する。新digit d_iは最後のsplit jにかかわらずd_i·dp_jとして加わるため、Σ_{j=0}^{i-1}dp_jだけ保持すればよい。dp_0=1は先頭から1blockを作るj=0の空prefixの積を表すが、i=1は一般式の10dp_0を含めず別初期化する。
採用する候補: dp_iの最後のsplitによる和を式変形し、dp prefix sumを持って一次漸化式で更新する。
全split候補の寄与を10dp_{i-1}+d_iΣdp_jへ集約し、N≤2×10^5を線形走査できる。
棄却する候補: 各末尾iで最後のsplit jを全列挙し、substring値を計算して加算する。
状態ごとにO(i)候補があり、合計O(N^2)になる。
棄却する候補: 2^{N-1}通りのsplit subsetを生成して積を求める。
split位置ごとの二択を直接列挙すると指数時間になる。
mod 998244353でdp_0=1、dp_1=d_1、prefix=dp_0+dp_1とする。i=2..Nについてdp_i=10dp_{i-1}+d_i·prefix(dp_0..dp_{i-1})を計算し、prefixへdp_iを加える。最後のdp_Nを出力する。
典型の発動条件
最後の区切り位置DP
発動条件: 列を連続blockへ分割した全結果を数え上げるとき。
最後のblock開始位置で場合分けしてprefix解と結合する。
式変形による遷移集約
発動条件: 全過去状態との遷移weightが桁追加などの共通漸化式を持つとき。
前段の答えとdp累積和へ二次和を圧縮する。
問題固有の要素
最後の数を1桁伸ばす操作と直前で新しくsplitする操作を、10倍項とdigit×全prefix解の項として一度に数えられる。
別の問題へ持ち帰る視点: 分割DPでは「最後のblockを延長」と「新blockを開始」の寄与が少数のaggregateで表せないか式を展開する。
正当性
最後blockへ次digitを連結すると各分割積の末尾因子は十倍されdp旧値の10倍を作る。次digitの加算寄与は全旧切れ目prefix積和に比例するので d_iΣdp_j。これに新block開始も含まれ、最後blockの切れ目分類で全分割を一度ずつ数える。
実装上の注意
- i=1へ一般漸化式を適用すると不要な10dp_0が入るため、base caseを分ける。
- 各乗算・加算をmodで正規化し、digitは文字から整数へ変換する。
復習の核
- 2桁abで分割なしの10a+bと分割ありのabが漸化式のどの項から出るか展開し、dp_0とdp_1の初期化を確認する。
計算量と制約
時間
桁数N。prefix和更新で O(N)。
空間
直前dpと累積和 O(1)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; X has N digits in decimal representation, none of which is 0.; All values in the input are integers.
出典