ABC461 F - Total Product is N

考え方

実際に数列を全部列挙するのは計算量的に非常に大変。
（……と思いきや、実はC++でなら工夫次第でどうにか間に合う。別解参照）

積が $N$ になるものを求める問題だが、実はそのものに限らず積が $N$ の約数になるものを求めるとよい。

約数を何個選んだかごとに、以下を求める。
積が $N$ の約数にならないものはスキップする。

• 選んだ約数の積で $N$ を割った商一覧
• 各商それぞれ、その商になるパターン数
• 各商それぞれ、その商になる単調増加数列のスコア合計

これは、使える約数を $1$ つずつ増やしながら、動的計画法でデータ構築していけばよい。
入力例1での動作参照。

構築出来たら、商が $1$ になったものに限り、スコアの処理をする。
使った約数の個数の階乗をかけることで、単調増加でない順の分もまとめて合計すれば答えとなる。

計算量の見積もりが難しいが、雑に見て $O(約数の個数^2\times 積で約数を作る平均長さ)$ くらい。
$10^{10}$ 以下だと、最も大変なもので $2304\times 2304\times 10くらい？$ なので間に合う。

入力例1での動作

入力を受け取る。

n: 8

$N=8$ の約数は $1,2,4,8$ である。

動的計画法では、約数を何個選んだかごとに、次の情報を管理する。

(残り, パターン数, 昇順限定でのスコア合計)

「残り」は、選んだ約数の積で $N$ を割った商である。

最初は何も選んでいないので、状態は次の $1$ つだけである。

0個: {(8, 1, 0)}

約数 $1$ を使えるようにする。
$1$ を選ぶと、残りは $8$ のままで、スコアに $1$ が加わる。

0個: {(8, 1, 0)}
1個: {(8, 1, 1)}

次に約数 $2$ を使えるようにする。
例えば、何も選んでいない状態から $2$ を選ぶと、残りは $8/2=4$、スコアは $2$ となる。
また、すでに $1$ を選んでいる状態から $2$ を選ぶと、残りは $4$、スコアは $1+2=3$ となる。

0個: {(8, 1, 0)}
1個: {(4, 1, 2), (8, 1, 1)}
2個: {(4, 1, 3)}

次に約数 $4$ を使えるようにする。

0個: {(8, 1, 0)}
1個: {(2, 1, 4), (4, 1, 2), (8, 1, 1)}
2個: {(1, 1, 6), (2, 1, 5), (4, 1, 3)}
3個: {(1, 1, 7)}

ここで残りが $1$ の状態が現れる。
例えば、$2$ 個選んだ (1, 1, 6) は、$2$ と $4$ を選んで積が $8$、スコアが $2+4=6$ となった状態である。

最後に約数 $8$ を使えるようにする。
$8$ を単独で選ぶと (1, 1, 8) ができる。
また、$1$ と $8$ を選ぶと (1, 1, 9) ができる。

一方、すでに $2$ と $4$ を選んだ状態も (1, 1, 6) である。
どちらも「$2$ 個選んで残りが $1$」という同じ状態になる。
そこで、パターン数とスコア合計をまとめる。

(1, 1, 9) + (1, 1, 6) → (1, 2, 15)

最終的な状態は次のようになる。

0個: {(8, 1, 0)}
1個: {(1, 1, 8), (2, 1, 4), (4, 1, 2), (8, 1, 1)}
2個: {(1, 2, 15), (2, 1, 5), (4, 1, 3)}
3個: {(1, 1, 7)}

積が $N$ になるのは、残りが $1$ の状態である。
ここまでは昇順に選んだ場合だけを数えているので、選んだ個数の階乗をかける。

したがって、答えは $8+30+42=80$ となる。

注意点

入力値 $N$ やその約数は、int 型からはみ出る。
long long 型を用いること。

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 する。

別解

積が $N$ になる $2$ 以上の要素からなる数列を、深さ優先探索で列挙してもよい。
計算量がかなり厳しいが、C++なら工夫すれば間に合う。

まず、$1$ を含む数列を列挙から外す。
$1$ がないデータから簡単に再現できるし、再現するまでもなく和に反映できる。

次に、単調減少数列のみ探す。
最初に選んだ数ではやめに残りに使える数を減らし、二分探索で次の約数のループ範囲を狭く絞る。
単調減少でないものは、数列の長さの階乗をかけることでまとめて反映できる。

これら $2$ つの工夫をすると、数列列挙でどうにか間に合う。