問題概要
整数 $n$ と長さ $n$ の正整数列 $a = (a_1, a_2, \dots ,a_n)$ が与えられる。
長さ $n$ の正整数列 $b = (b_1, b_2, \dots ,b_n), d = (d_1, d_2, \dots ,d_n)$ を、 $a_i$ が $b_i$ の倍数であり、かつ $b_i$ が $d_i$ の倍数であるように作る。このとき $\displaystyle \prod_{i=1}^{n} d_i ^2 \gt \prod_{i=1}^{n} b_i$ であるような選び方を $\bmod 998244353$ で数え上げよ。
制約 : $n \leq 100, 1 \leq a_i \leq 10^9$
ある素数 $p$ があり $a_i$ が全て $p$ のべき乗であるようなケースに 30 点くらいついている。
解法
一つ気がつけば系のネタではあるが、面白かった。書いてあるものをそのままは数えづらい。
$b$ を固定して考えてみる。重要な気づきとして、 $\displaystyle \prod_{i=1}^{n} d_i ^2 \gt \prod_{i=1}^{n} b_i$ であるような選び方と、 $\displaystyle \prod_{i=1}^{n} d_i ^2 \lt \prod_{i=1}^{n} b_i$ であるような選び方の個数は等しい。
では $\displaystyle \prod_{i=1}^{n} d_i ^2 = \prod_{i=1}^{n} b_i$ であるような選び方はどのようなものかというと、 $a_i$ の素因数として登場する全ての素数について、 $b, d$ で出てくる回数がぴったり $2 : 1$ である、という条件になる。
選び方の総数を $x$ とし、また $\displaystyle \prod_{i=1}^{n} d_i ^2 = \prod_{i=1}^{n} b_i$ を満たすような選び方の総数を $y$ とする。答えは $\displaystyle \frac{x + y}{2}$ になる。あとは $x, y$ を求めれば良い。
これはもう素因数ごとの問題として分割して解ける。$x$ はとても簡単。$y$ は dp をする必要がある。自分の解法だと計算量は $O(n^3 \log^3 \max A)$
雑記
小課題がちょっと誘導ではあった。単独で ARC-D,E くらいに出ていそう。
コメント