题解 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}$](https://www.cnblogs.com/cj-xxz/p/10632172.html)