AtCoder Regular Contest 182 C問題メモ
C - Sum of Number of Divisors of Product
問題文
- 長さが 1 以上 N 以下で各要素が 1 以上 M 以下である整数列を良い数列と呼びます。
- また、良い数列に対するスコアを、その整数列に含まれる要素の総積を X としたときの、X の正の約数の総数とします。
- 良い数列は N∑k=1Mk 個ありますが、それらすべてに対するスコアの総和を 998244353 で割った余りを求めてください。
制約
- 1≤N≤1018
- 1≤M≤16
- 入力はすべて整数
解法
積の和典型。
いつも解答見て「お前だったのか」って言ってる気がする。
X の約数の個数は、X を pa11pa22... と素因数分解したときの (a1+1)(a2+1)... で求められる。
M が小さいので、考えられる素因数は (2,3,5,7,11,13) の6つのみである。
元の問題は、以下の問題に言い換えられる。
- 以下の試行を考える
- 素因数に対応した箱を最大6つ用意し、はじめに1つずつボールを入れておく
- 以下を 1回以上 N 回以下繰り返す
- 1~M の数を1つ決め、その素因数に従って箱にボールを入れる
- 2 を選んだら 2 の箱に1個入れる
- 4 を選んだら 2 の箱に2個入れる
- 12 を選んだら 2 の箱に2個、3 の箱に1個入れる
- 最終的な各箱に入ったボールの個数の積が、X の正の約数の個数である
- 全ての操作列に対する答えの総和を求めよ
これは、更に X の正の約数の個数は「最終的な各箱に入ったボールから1つずつ選んで黒く塗る方法の個数」と言い換えられる。
さらに、試行の過程で「ボールを箱に入れるとき、同時にボールを塗る/塗らないも決めちゃう」としてもよい。
既に塗られたボールの入った箱の集合 S をもってDPすれば、 最終的に全ての箱に黒いボールが1つずつ入っている状態が、X の正の約数の個数と一致する。
で、このDPの遷移を考えると、「S が同じ状態は、各箱にボールが何個入っていようが、その後の遷移が同じ」とわかる。
制約の大きい厄介な N の影響の大部分が無視できる。
よって、以下のDPが成り立つ。
- DP[i,S]=i 番目の数字まで決めて、既に黒く塗られたボールの入った箱の集合が S である場合の数
これだとまだ O(N2π)(π は M 以下の素因数の個数=6)かかるが、 このDPは ある Sx から Sy への遷移が i に依らず一定なので、行列累乗で高速化できる。
N 以下を求める
ちょうど N 回なら単に S の状態数 2π×2π の行列累乗でいいが、 今回は「N 回以下」を求める必要がある。
これは、行・列に1段追加して、以下のようにすればよい。
˜A=(A11A12…A12π0A21A22…A22π0⋮⋮⋱⋮⋮A∗A∗…A∗0A∗A∗…A2π2π100001)
(全部の添字を書くと面倒ごちゃごちゃになるので、適当に省略)
これで、「途中で全て選ばれた状態 S=2π になったら、右端列に適宜加算される」という遷移がなされるようになる。
最終的に、˜AN+1 の 1~2π 行目の右端列の総和が答えとなる。
(N 回ちょうどまでの結果も右端に加算するため、1回多く累乗する)
O(8πlogN) となる。