题解 P3704 【[SDOI2017]数字表格】

· · 题解

这道题目还有一种比较有意思的解法。

定义一种运算(\mathbf f\oplus\mathbf g)(x) = \prod\limits_{d\mid x}\mathbf f(d)^{\mathbf g(\frac xd)}

研究一下这种运算的性质：

虽然这个运算没有交换律也没有结合律，但是它有一个比较奇特的性质：

设运算*是狄利克雷卷积，那么可以证明(\mathbf f \oplus \mathbf g) \oplus \mathbf h = \mathbf f \oplus (\mathbf g * \mathbf h)。

于是就有一种基于\prod的莫比乌斯反演：

\mathbf f = \mathbf g \oplus \mathbf 1 \Rightarrow \mathbf g = \mathbf f \oplus \mu

也就是\mathbf f(x) = \prod_{d|x} \mathbf g(d) \Rightarrow \mathbf g(x) = \prod_{d|x} \mathbf f(d)^{\mu(\frac xd)}

那么这道题目就很好推了。

\begin{aligned}&\prod_{i=1}^n\prod_{j=1}^m f[\gcd(i, j)] \\=&\prod_{i=1}^n\prod_{j=1}^m\prod_{d|i, d|j} \mathbf g(d) \quad (\mathbf g = \mathbf f \oplus \mu) \\=&\prod_{d=1}^n \mathbf g(d)^{\sum_{d|i}\sum_{d|j}1} \\=&\prod_{d=1}^n \mathbf g(d)^{\left\lfloor \frac nd\right\rfloor \left\lfloor \frac md\right\rfloor}\end{aligned}

我们发现\mathbf g可以\mathrm{O}(n\log n)算，于是就做完了。

代码见我的\texttt{blog}