ABC461 F - Total Product is N

総乗はN

考え方

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

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

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

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

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

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

入力を受け取る。

n: 8

$N$ の約数を全列挙する。

d: {1, 2, 4, 8}

(残り, パターン数, 昇順限定でのスコア合計) を約数の個数ごとに管理するデータを用意する。
最初に、空集合を選んだ場合として、$(N,1,0)$ を入れておく。

0 個選ぶ場合: {(8,1,0)}
1 個選ぶ場合:
2 個選ぶ場合:
3 個選ぶ場合:
4 個選ぶ場合:

$1$ を選んだ場合のデータを追加する。

0 個選ぶ場合: {(8,1,0)}
1 個選ぶ場合: {(8,1,1)}
2 個選ぶ場合:
3 個選ぶ場合:
4 個選ぶ場合:

$2$ を選んだ場合のデータを追加する。
各配列はマージソート的な処理で「残り」の値の昇順に保つ。

0 個選ぶ場合: {(8,1,0)}
1 個選ぶ場合: {(4,1,2), (8,1,1)}
2 個選ぶ場合: {(4,1,3)}
3 個選ぶ場合:
4 個選ぶ場合:

$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)}
4 個選ぶ場合:

$8$ を選んだ場合のデータを追加する。
残りを $8$ で割り切れないものはスキップする。
$\{1,8\}$ と $\{2,4\}$ は同じ個数で同じ残りになるので、パターン数とスコア合計を足す。
つまり、$(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)}
4 個選ぶ場合:

最終的に、残りが $1$ になっているものだけを答えに加算する。
昇順限定で数えているため、選んだ個数の階乗倍をする。

1 個選ぶ場合: 8 * 1! = 8
2 個選ぶ場合: 15 * 2! = 30
3 個選ぶ場合: 7 * 3! = 42
result: 80

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

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

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

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

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

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