上限制約付き桁DP
概要
数値上限以下の桁列を接頭辞から構成し、tight・started・剰余・digit maskなど将来に必要な有限統計を保つ。
考え方
上限の各桁とまだ一致するかをtightフラグで持つ。一度小さくなれば残りの桁は自由に選べる。桁和や剰余など未来に必要な情報だけを追加する。
初期値はdp[0][tight=1][started=0][初期統計]=1。次の桁dはtightなら上限桁以下、それ以外は0,…,b−1から選ぶ。newTight=tight AND(d=上限桁)、newStarted=started OR(d≠0)。数値の剰余rは (br+d) mod m、桁和はs+dへ更新する。digit maskは先頭0を実桁とみなさないならstartedが立ってから更新する。条件を満たす最終状態の個数を両tightについて足す。数0だけは全桁が先頭0となるので、0の数字表現を条件へどう含めるかを別に判定する。
値の総和も持つなら各状態に(count,sum)を保存する。次の桁dへの寄与は count'=count、sum'=b·sum+d·count。同じ遷移先へ加算すれば、候補数を列挙せず総和を求められる。
成立条件と計算量
L桁・基数b・追加状態SならO(LbS)。先頭0を実際の桁として数えるかは問題による。区間はF(R)−F(L−1)で求め、L=0の境界を扱う。巨大上限は文字列で読み整数overflowを避ける。
問題一覧
- ABC406 E「Popcount Sum 3」 公式問題
- ABC465 E「Digit Circus」 公式問題
- ABC336 E「Digit Sum Divisible」 公式問題
- ABC235 F「Variety of Digits」 公式問題
- ABC317 F「Nim」 公式問題組合せ: 包除・Möbius反転で重複を補正する
技能・出典
主題: 上限制約付き桁DP(数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。)。既習技能: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。 - ABC288 Ex「A Nameless Counting Problem」 公式問題
技能・出典
主題: 上限制約付き桁DP(数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。)。既習技能: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 上限制約付き桁DP / 補助タグ: 組合せ係数・数え上げ、集合上の包除原理
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。tight・先頭の0・残す統計を分け、上限以下の整数を重複なく数える。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 接頭辞から更新する有限状態DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-digit-dp
上限制約付き桁DP
習得する技能
- 数値上限とのtight・先頭ゼロ・剰余・digit maskなどを接頭辞ごとに更新し、条件を満たす数の個数または値の総和を求められる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する。
このUnitを直接前提とする単元: なし。
接頭辞状態DPの共通像を得た後、数値上限とのtight・started・剰余・digit maskだけを状態にして、上限以下の整数を数える。
このUnitでは扱わないもの
- 上限制約付き桁DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。