Xmas Contest 2020 D
lsj2009
·
·
题解
$$
B_{i,j}=\begin{cases}
1-c & i=j\\
-c & i\ne j\wedge i\mid j\\
0 & \text{otherwise}
\end{cases}
$$
将 $\det{A}$ 展开，有 $(-1)^{\tau(p)}\prod\limits_{1\le i\le n}\left(B_{i,p_i}+C_{i,p_i}\right)$ 对答案产生贡献，在 $i$ 行中仅有 $p_i$ 值有意义；若将 $\prod$ 再展开，钦定 $i\in S$ 中 $B_{i,p_i}$ 产生贡献，否则是 $C_{i,p_i}$，即可得到 $\det{A}$ 的另一种算法：选取 $S\subseteq[n]$，对于所有 $i\in S$，将 $B_{i,*}$ 全体替换为 $C_{i,*}$ 得到矩阵 $B'$，求 $\det{B'}$ 之和。由于 $\operatorname{rank}(C)=1$，故若 $|S|>1$ 则 $B'$ 存在两行相同，则行列式为 $0$，则仅有 $|S|\le 1$ 情况下对答案有贡献。
而 $B$ 是一个上三角矩阵，故 $\det{B}=(1-c)^n$，也即 $S=\emptyset$ 时的贡献；当 $|S|=1$ 时，若选取第 $k$ 行替换，考察 $i\to p_i$ 形成的若干置换环，发现除 $k$ 所在环外其余环均为自环，而 $k$ 所在环形如，除 $k$ 之外，其余点均为其后继点的因数。
令 $f_k$ 表示替换第 $k$ 列的答案：
- 若 $p_k\ne k$：枚举 $k$ 的所有因数 $d(d\ne k)$，找到 $d$ 所在置换环，若 $d$ 后继节点为 $x$，由于 $d$ 原本是环上最大值，而 $k>d$ 故 $k$ 原本必是孤立点，则断边 $d\overset{c}{\longrightarrow}x$ 和 $k\overset{1-c}{\longrightarrow}k$，加边 $d\overset{-c}{\longrightarrow}k\overset{c}{\longrightarrow}x$，这是所有 $d$ 的方案向 $k$ 的映射，倒着射回去也一样，故我们将所有 $d$ 的方案和 $p_k\ne k$ 情况下的方案构成了双射！再分析 $\tau(p)$ 的变化，由于环个数恰好减一（并入一孤立点），则 $\tau(p)$ 在模 $2$ 意义下变化 $1$，这一结论我们在 AGC070B 中已有推导。
- 若 $p_k=k$：则 $k\to k$ 的边权由 $1-c$ 变为 $c$。
依照边权和行列式系数 $(-1)^{\tau(p)}$ 的变化，则可得到转移方程：
$$
f_k=\frac{c}{1-c}\left(1+\sum\limits_{d\mid k,d\ne k}f_d\right)
$$
欲求 $\sum\limits_{1\le k\le n} f_k$。$n$ 很大，感觉肯定要用到一些筛子相关了。令 $g_k=[k=1]-c$，则有 $\forall k,(f\times g)_k=c$，故可以杜教筛计算。预处理 $\le B$ 的 $f$ 进行优化，则复杂度为 $B\log{B}+\frac{n}{\sqrt{B}}$，取 $B=\left(\frac{n}{\log{n}}\right)^{2/3}$，得最终复杂度 $\mathcal{O}(n^{2/3}\log^{1/3}{n})$。