考察
条件n mod digitSum(n)=0ではmodulus自体が桁選択で変わるため、そのまま一つの桁DP状態に入れにくい。先に最終桁和sを固定すれば、桁和sかつn mod s=0という通常の有限状態DPになる。
採用する候補: 可能な桁和sを全探索し、各sについて桁和・剰余付きdigit DPを行う
最大桁和は高々9×桁数で小さく、変動する除数を外側loopへ分離できる。
棄却する候補: 1からNまで各整数の桁和と剰余を直接調べる
Nは10^14まであり線形列挙できない。
固定したsごとに、上位d桁までのdigit sum i、値mod s=j、Nのprefixと一致中か未満かを持てば、次digit tで(i+t,(10j+t) mod s)へ遷移できる。最終状態(i,j)=(s,0)だけがそのsのgood整数を数える。
Nをdecimal digit列にし、s=1から9×桁数まで繰り返す。dp[pos][sum][rem][tight]を0初期化しdp[0][0][0][1]=1、許される次digitを配る。全桁後のdp[L][s][0][0/1]を加算する。
典型の発動条件
parameter固定によるdigit DP
発動条件: 桁から決まる値が同時にmodulusとして使われ、状態遷移の法が未確定である。
最終digit sum sを外側で固定し、各DP内では剰余状態0,…,s-1を使う。
上限制約付き桁DP
発動条件: 0≤n≤Nのうち桁和と剰余条件を満たす個数を数える。
tight flagでN prefixとの大小を持ち、leading zeroを許して固定長列として処理する。
問題固有の要素
各正整数は桁和sをただ一つ持つので、sごとの数え上げは重複せず、その和が答えになる。
別の問題へ持ち帰る視点: 状態遷移のmodulusや目標値が対象自身から決まる場合、取り得る小範囲を外側列挙すると通常DPへ戻せる。
正当性
正整数xは桁和sを一意に持つので、sを固定した対象集合は互いに重複しない。digit DPは処理済み桁の桁和・x mod s・Nのprefixとの比較を持ち、次digit dで和へd、剰余へ10r+dを加える。これらは条件判定に必要十分で、全digit列を一度だけ表す。最後に桁和sかつ剰余0を取ると、ちょうどxがその桁和で割り切れる条件になる。leading zeroは一意のpaddingであり、s≥1なので整数0は受理されない。全sの和が求める個数である。
実装上の注意
- leading zeroで表した0はs≥1の最終桁和条件を満たさず自動除外される。sum>sの遷移を切り、N=10^14でも安全な最大sを桁数から取る。
復習の核
- 小さいNで1…Nを直接列挙し、9の繰上がり境界、N自身を含むtight状態、桁和1・最大付近のsを比較する。
計算量と制約
時間
O(D(9D)³)、DはNの十進桁数、固定sのsum×remainder状態を全sで走査。
空間
O((9D)²)、pos方向rolling。
制約との対応
公式制約の確認範囲: Time limit: 10 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{14}; N is an integer.
出典