自动搬运

查看原文

来自洛谷，原作者为

	Prean 不断倒下，不断站起来，不停地与自己作斗争

搬运于2025-08-24 22:34:00，当前版本为作者最后更新于2021-10-04 19:07:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置芝士的光速幂技巧。

本题解不是正解，和正解唯一的差别在于对幂的处理。

我们能够发现有：

$$F(n,m,k)=\frac 1 n \binom {n+m-1} m$$

证明见这里。

然后我们开始推柿子：

$$\prod_{i=1}^n\prod_{j=1}^m\prod_{x=0}^k(\frac 1 i \binom {i+j-1} j )^{[\gcd(i,j)=1]} $$$$(\prod_{i=1}^n\prod_{j=1}^m(\frac {(i+j-1)!} {i!j!})^{[\gcd(i,j)=1]})^{k+1} $$

此时我们可以把答案拆成两部分：

$$\prod_{i=1}^n\prod_{j=1}^m((i+j-1)!)^{[\gcd(i,j)=1]} $$$$\prod_{i=1}^n\prod_{j=1}^m(i!j!)^{[\gcd(i,j)=1]}$$

1

$$\prod_{i=1}^n\prod_{j=1}^m((i+j-1)!)^{\sum_{d|i,d|j}\mu(d)} $$$$\prod_{d=1}^n\prod_{i=1}^{\lfloor \frac n d \rfloor}\prod_{j=1}^{\lfloor \frac m d \rfloor} (di+dj-1)!^{\mu(d)} $$$$\prod_{d=1}^n\prod_{i=1}^{\lfloor \frac n d \rfloor}\prod_{j=1}^{\lfloor \frac m d \rfloor} \frac {(d(i+j))!^{\mu(d)}} {(d(i+j))^{\mu(d)}} $$

1.1

$$\prod_{d=1}^n\prod_{i=1}^{\lfloor \frac n d \rfloor}\prod_{j=1}^{\lfloor \frac m d \rfloor} {(d(i+j))!^{\mu(d)}} $$

真正的毒瘤。

$$\prod_{d=1}^n\prod_{k=1}^{{\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}}(dk)!^{num_{{\lfloor \frac n d \rfloor},{\lfloor \frac m d \rfloor}}[k]\mu(d)} $$$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac n d \rfloor}(dk)!^{(k-1)\mu(d)} \times\prod_{k={\lfloor \frac n d \rfloor}+1}^{{\lfloor \frac m d \rfloor}} (dk)!^{{\lfloor \frac n d \rfloor}\mu(d)} \times \prod_{k={\lfloor \frac m d \rfloor}+1}^{{\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}} (dk)!^{({\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}-k+1)\mu(d)} $$

1.1.1

$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac n d \rfloor} (dk)!^{(k-1)\mu(d)} $$$$\prod_{d=1}^nd!^{\sum_{k|d} k \mu(\frac d k)} \div \prod_{d=1}^n d!^{\sum_{k|d}\mu(\frac d k)} $$$$\prod_{d=1}^nd!^{\varphi(d)}$$

有趣的一点是，这玩意儿和 $ \prod_{d=1}^n\prod_{k=1}^{\lfloor \frac n d \rfloor} (dk)!^{k\mu(d)} $ 是一个东西。以及这玩意儿和后面的 $1.1.3.1$ 是一样的，所以可以不用推。。。

1.1.2

$$\prod_{d=1}^n\prod_{k={\lfloor \frac n d \rfloor}+1}^{\lfloor \frac m d \rfloor} (dk)^{{\lfloor \frac n d \rfloor}\mu(d)} $$$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac m d \rfloor} (dk)^{{\lfloor \frac n d \rfloor}\mu(d)} \div \prod_{k=1}^{\lfloor \frac n d \rfloor} (dk)!^{{\lfloor \frac n d \rfloor}\mu(d)} $$

右边：

$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac n d \rfloor} (dk)!^{\mu(d){\lfloor \frac n d \rfloor}} $$$$\prod_{d=1}^n(\prod_{k=1}^{\lfloor \frac n d \rfloor} (dk)!^{\mu(d)})^{\lfloor \frac n d \rfloor} $$

设：

$$f_1(d,n)=\prod_{k=1}^n(dk)!^{\mu(d)}$$

可以发现：

$$f_1(d,n)=f_1(d,n-1) \times (dn)!^{\mu(d)}$$

$(dn)!^{mu(d)}$ 用光速幂搞定，（这里的 $dn$ 一定不大于数据范围）就可以 $O(n \log n)$ 递推 $f_1$ 了。

这一部分最终能够推得：

$$\prod_{d=1}^n f_1(d,{\lfloor \frac n d \rfloor})^{\lfloor \frac n d \rfloor} $$

对 $f_1$ 在第二维度上做前缀积即可整除分块带走。

左边的和右边的是一样的，就不再论述了。

1.1.3

$$\prod_{d=1}^n\prod_{k={\lfloor \frac m d \rfloor}+1}^{{\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}} (dk)!^{({\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}-k+1)\mu(d)} $$

它 是 毒 瘤

首先拆一下：

$$\prod_{d=1}^n((\prod_{k=1}^{{\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}} (dk)!^{({\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor})\mu(d)} \div \prod_{k=1}^{\lfloor \frac m d \rfloor} (dk)!^{({\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor})\mu(d)}) $$$$\div (\prod_{k=1}^{{\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}} (dk)!^{k\mu(d)} \div \prod_{k=1}^{\lfloor \frac m d \rfloor} (dk)!^{k\mu(d)}) $$$$\times (\prod_{k=1}^{{\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor}} (dk)!^{\mu(d)} \div \prod_{k=1}^{\lfloor \frac m d \rfloor} (dk)!^{\mu(d)})) $$

后面四个好像容易一些，先搞后面四个。

1.1.3.1

$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac m d \rfloor}(dk)!^{k\mu(d)} $$

设：

$$f_2(d,n)=\prod_{k=1}^n(dk)!^{k\mu(d)}$$

明显有：

$$f_2(d,n)=f_2(d,n-1) \times (dn)!^{n\mu(d)}$$

和 $f_1$ 一样即可以 $O(n\log n)$ 处理这玩意儿。

1.1.3.2

$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac m d \rfloor} (dk)!^{\mu(d)} $$

你发现这玩意儿就是 $f_1$，所以可以直接草了。

1.1.3.3

$$\prod_{d=1}^n\prod_{k=1}^{\lfloor \frac m d \rfloor} (dk)!^{({\lfloor \frac n d \rfloor}+{\lfloor \frac m d \rfloor})\mu(d)} $$

这玩意儿好像就只是 $f_1$ 加上了一个幂？用一个光速幂就可以带走了。

1.2

$$\prod_{d=1}^n\prod_{i=1}^{\lfloor \frac n d \rfloor}\prod_{j=1}^{\lfloor \frac m d \rfloor} {(d(i+j))^{\mu(d)}} $$

这一部分几乎和 $1.1$ 是相同的，所以不再论述，将 $(dk)!$ 换成 $(dk)$ 即可。

2

$$\prod_{i=1}^n\prod_{j=1}^m(i!j!)^{\sum_{d|i,d|j} \mu(d)} $$

其实这一部分明显比前面简单得多，以至于我前面刚写完就以为整个题解写完了（

$$\prod_{d=1}^n\prod_{i=1}^{\lfloor \frac n d \rfloor}\prod_{i=1}^{\lfloor \frac m d \rfloor}(di)!^{\mu(d)}(dj)!^{\mu(d)} $$$$\prod_{d=1}^n(\prod_{i=1}^{\lfloor \frac n d \rfloor}(di)!^{\mu(d){\lfloor \frac m d \rfloor}} \times \prod_{i=1}^{\lfloor \frac m d \rfloor}(dj)!^{\mu(d){\lfloor \frac n d \rfloor}}) $$$$\prod_{d=1}^n(\prod_{i=1}^{\lfloor \frac n d \rfloor} (di)!^{\mu(d)})^{\lfloor \frac m d \rfloor} \times (\prod_{d=1}^n \prod_{j=1}^{\lfloor \frac m d \rfloor} (dj)!^{\mu(d)})^{\lfloor \frac n d \rfloor} $$

我们发现这玩意儿就是 $f_3$，直接光速幂即可。

虽然复杂度是 $O(n^{\frac 5 4}\log n+T\sqrt n)$ 的，但是常数巨大。。。

以及，光速幂空间过大，所以可能需要 $\rm vector$ 来实现，以及离线卡常。

来想想需要对哪些东西预处理光速幂

$f_1$和 $1.2$ 中的 “$f_1$”。长度分别为 $O(n\log n)$ 和 $O(n\log n)$。

对二者同时光速幂。注意光速幂离线后一共有 $O(n\log n)$ 个底数，对其分块后可以卡进 cache，对上面的二者同步预处理光速幂即可。