ABC 288 F — Integer Division

考察

最後の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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Integer Division の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: prefix分割DP

主題
  • prefix分割DP: 列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: prefix分割DP

    補助タグ: DP遷移の集約・高速化

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: prefix分割DP

    • 列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題