Xmas Contest 2020 D

$A$ 中非 $c$ 位置较少，将其分解为 $B$ 与全 $c$ 矩阵 $C$ 之和，则

将 $\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$ 列的答案：

依照边权和行列式系数 $(-1)^{\tau(p)}$ 的变化，则可得到转移方程：

欲求 $\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})$。