ABC 461 F — Total Product is N

考察

積がNになる選択要素は全てNの約数で、要素数bも小さい。unordered tupleの選択を数えた後にb!を掛ければ順序付き列へ戻せる。dp1のselect遷移は旧score総和に、全旧選択それぞれへ新値d_aを足す項 dp0×d_a を加える。1を含めてもdistinct約数を一度ずつ選ぶ0/1 DPなので、選択個数は積制約から14以下に限定できる。

採用する候補: Nの約数d_aを列挙し、選択個数b・現在積cごとに選び方数dp0と選択値総和dp1を持つ0/1 knapsackを行う。

d_aを選べるのはcがd_aの倍数の場合だけで、遷移元積c/d_aも約数である。N≤10^10では約数数≤2304、b≤14なので状態数が収まる。

棄却する候補: 積Nとなる順序付き正整数列を全factorization treeとして列挙する。

factorの順序分岐と長さ分岐が大きく、同じmultisetをb!回重複して探索する。

全約数をsortし積値からindexへのmapを作る。各dについてbを降順、積cを走査し、c%d=0ならdp0[b][c]+=old0[b-1][c/d]、dp1+=old1+old0×d と更新する。Σ_b dp1[b][N]b!を返す。

典型の発動条件

約数集合上の積knapsack

発動条件: 選択要素の総積が固定Nで、候補がNの約数に限られるとき。

積stateを約数indexへ圧縮して0/1選択する。

個数とscore総和の同時DP

発動条件: 全組合せの個数だけでなく選択値和などの総scoreが必要なとき。

count×新規寄与をscore遷移へ追加する。

問題固有の要素

積制約DPでは値域を1..Nで持たず、到達し得るNの約数だけへ圧縮する。

別の問題へ持ち帰る視点: 順序付きobjectを直接列挙せず、distinct要素multisetを数えて最後にfactorialで順序を付ける。

正当性

積Nの各要素は約数であり、相異なる条件から約数を0/1選択する。dp0は選択個数と積別の個数、dp1はその全score和。約数dを追加すると各旧集合のscoreにdが足されるので新score和はold1+d×old0。非採用と採用を併合する帰納法で集合を一度ずつ数える。b個の相異なる要素はちょうどb!通りに並べ替えられscoreは不変。従ってdp1[b,N]b!の総和が全列score。b個の異なる正数の積は最低b!なのでBで打ち切れる。

実装上の注意

  • 0/1 DPなのでd処理中のbは降順に回し同じ約数を再利用しない。b=0のscore0基底とmod積を正しく置く。

復習の核

  • 一要素dを追加した全選択のscore和が old1+old0×d になることと、最後のb!の意味を小さいNで確認する。

計算量と制約

時間

D=約数個数、B=max{b:b!≤N}≤13。試し割り約数列挙O(√N)、dp O(BD²)。hash indexなら期待O(√N+BD²)、index対応を前計算して配列参照なら確定的O(√N+D²log D+BD²)。

空間

二DP O(BD)、商index全pair前計算を持つならO(D²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{10}; The input value is an integer.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Total Product is N の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 資源・容量DP

主題
  • 資源・容量DP: 資源軸の上限と更新順を選び、選択の重複を避けられる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 資源軸knapsack DP

    補助タグ: 素因数・約数分解

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

    学習の位置

    体系上の位置: 資源・容量DP

    • 資源軸の上限と更新順を選び、選択の重複を避けられる。

    先に読む単元:

    この解説で扱わないこと:

    • 使用済み要素集合そのものを状態とし、容量・個数の値軸を持たないDP。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題