より詳しい解説：https://hos-lyric.hatenablog.com/entry/2021/01/14/201148

対角の \(1\) を \(C + (1 - C)\) だと思って，行列式の定義においてどこの \(1 - C\) を使うかで場合分けします．

\(\{1, \ldots, n\}\) の部分集合 \(S\) について，\(A - (1 - C) I_N\) から添え字が \(S\) に含まれる成分のみを取り出した行列の行列式を考えることになります．\(S = \emptyset\) のときは \(1\) です．\(S\) のすべての元の公倍数が \(S\) に含まれる場合は，それを取り除いたときの値の \(C\) 倍です．それ以外のときは行列式が \(0\) となることがわかります．

よって \(\det A\) は，\(\{1, \ldots, n\}\) の部分集合 \(S\) であって整除関係について全順序であるようなものすべてについての \(C^{\lvert S\rvert} (1 - C)^{N-\lvert S\rvert}\) の和となります．

\(r = \frac{C}{1 - C}\) とおいて (\(C = 1\) のときは例外処理します)，\(f(n)\) を整数列 \(1 = x_0 < x_1 < \cdots < x_k \le n\) であって \(x_0 \mid x_1 \mid \cdots \mid x_k\) を満たすものすべてについての \(r^k\) の和とおきます．答えは \(f(N)\) から求められます．

\(f(n) = 1 + r \sum_{i=2}^n f(\lfloor n/i \rfloor)\) という漸化式が得られます．この DP は Xmas Contest 2019 D 問題と同様に \(O(N^{3/4})\) 時間で処理できます．