Xmas Contest 2020 D: Determinant 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_d

問題概要

$N \times N$ 行列 $A$ の $(i, j)$ 成分は

$i = j$ のとき $1$
$i \nmid j$ のとき $C$
$i \ne j$ かつ $i \mid j$ のとき $0$

である． $(\det A) \bmod 998244353$ を求めよ．

行列式の処理

対角だけ変なことになっているので，対角をどう使うかで場合分けします． $1 = C + (1-C)$ だと思って，行列式の定義の各項 ( $N$ 個の成分の積) のうちどの対角で $1-C$ の部分をとるかという場合分けをします．別の言い方をすると， $(i, i)$ 成分に $C + x_i$ が書いてあると思って，行列式を $x_1, \ldots, x_N$ の多項式として書いて各係数を求めるということです．なお，なぜ $1 = 0 + 1$ でなく $1 = C + (1-C)$ なのか (なぜ $x_i$ でなくて $C + x_i$ なのか) は，いろいろ試してみてうまくいくほうを選びましょうというより多くのことは言えなさそうです．

まとめると， $A$ の対角を $1-C$ に置き換えた行列を $B$ とし， $S \subseteq \{1, \ldots, N\}$ に対し $i, j \in S$ なる成分だけ取り出した行列 (主小行列) を $B_S$ となります． $\det A = \sum_{S\subseteq\{1,\ldots,N\}} (1-C)^{N-\lvert S\rvert} \det B_S$ となります． $\det B_S$ の例を載せます．

$\begin{align} B_{\{1, 2, 10, 20, 60\}} &= \begin{bmatrix} C&0&0&0&0 \\ C&C&0&0&0 \\ C&C&C&0&0 \\ C&C&C&C&0 \\ C&C&C&C&C \end{bmatrix}, \\ B_{\{1, 2, 14, 20, 60\}} &= \begin{bmatrix} C&0&0&0&0 \\ C&C&0&0&0 \\ C&C&C&C&C \\ C&C&C&C&0 \\ C&C&C&C&C \end{bmatrix} \end{align}$

$B_\emptyset = 1$ です．ある $j \in S$ があって $S$ の任意の元が $j$ を割り切るとき， $j$ の列が対角だけ $C$ で他が $0$ なので， $\det B_S = (\det B_{S \setminus \{j\}}) \cdot C$ となります．そうでないとき， $S$ には整除関係について極大な (つまり，他の $S$ を割り切らない) 相異なる $2$ 元 $i, i'$ がとれますが， $i, i'$ の行はともに全部 $C$ なので， $\det B_S = 0$ です．

というわけで $S$ が整除関係について全順序な (つまり，どの $2$ 元も一方が他方を割り切る) とき $\det B_S = C^{\lvert S\rvert}$ ，そうでないとき $\det B_S = 0$ です．よって，整除関係について全順序であるような $\{1, \ldots, N\}$ の部分集合をその大きさごとに係数をかけて数える問題になりました．

数え上げ

$C = 1$ のときは $S = \{1, \ldots, N\}$ が全順序かどうかになるので， $N \le 2$ のとき $1$ で $N \ge 3$ のとき $0$ が答えになります．

$C \ne 1$ のときは $r = \frac{C}{1-C}$ とおいて係数を $r^{\lvert S\rvert}$ とみると考えやすいのでそうします．全順序な $S$ のうち， $1$ を含むものと含まないものがちょうど対応するので，片方だけ数えると楽です． $F(n)$ を，整数列 $1 = i_0 \lt i_1 \lt \cdots \lt i_k \le n$ であって $i_0 \mid i_1 \mid \cdots \mid i_k$ なるものについての $r^k$ の和とすると， $\det A = (1-C)^N (1+r) F(N)$ です． $k = 0$ なものは $1$ 通りで，そうでないものは $i_1$ で分類して， $1 = \frac{i_1}{i_1} \lt \cdots \lt \frac{i_k}{i_1} \le \left\lfloor\frac{n}{i_1}\right\rfloor$ が $1$ つ短い列に対応するので，漸化式 $F(n) = 1 + r \sum_{i=2}^n F\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ が得られます．

これをそのまま DP すると $O(N^2)$ 時間かかりますが， $\left\lfloor\frac{n}{i}\right\rfloor$ が同じ部分をまとめれば $O(N^{3/2})$ となります (20 点)．さらに， $F(N)$ を求めるのに必要な $F(n)$ は $n = \left\lfloor\frac{N}{i}\right\rfloor$ と書けるもののみであることに注意します．これで計算量を $N^{1/2}$ の前後で分けて評価すると $O(N^{3/4})$ であることがわかります．これは，Xmas Contes 2019 D 問題と同様なのでこちらで詳しく解説しています．

数え上げ (別解)

上の方法では $S$ の最小元だけ $1$ に固定し最大元は動かして考えていましたが，最大元も固定して考えるのも自然かもしれません． $f_k(n)$ を，整数列 $1 = i_0 \lt i_1 \lt \cdots \lt i_k = n$ であって $i_0 \mid i_1 \mid \cdots \mid i_k$ なるものの個数とします． $F(N) = \sum_k r^k \sum_{n=1}^N f_k(n)$ です．

$k \ge 1$ を固定すると，これは $k$ 個の不等号 $\lt$ の条件を「 $\le$ だが $=$ でない」と読んで包除することで，各素因数について条件が独立になって数えられます．具体的には， $n$ の素因数分解を $n = \prod_m p_m^{e_m}$ として $f_k(n) = \sum_{l=1}^k (-1)^{k-l} \binom{k}{l} \prod_m \binom{e_m+l-1}{l-1}$ です．

これで各 $n$ について計算すれば 20 点です．100 点をとるには，以下のような工夫が考えられます：

$f_k(n)$ は入力に依存しないので，累積和を適当な間隔で埋め込む (結構大変だと思います)．
$f_k(n)$ は素因数分解の指数の多重集合にしか依存しないので，同じ値を複数回計算しない ( $N = 10^9$ で $1324$ 通りになります)．素因数分解の指数の列が同じ $n$ をうまくまとめて数える (詳細は省略しますが，高速素数カウントを用いて最大素因数だけ異なる数をまとめて処理することができます)．