题解：P7890 「MCOI-06」Lost Desire
cforrest
·
·
题解
提供另一种推式子的方法。
如同其他题解解释的那样，求出原根 g 后，问题转化为计算离散对数
K\sum_{m=1}^M\sum_{n=1}^N[m\perp n]\log_g\dfrac{(m+n-1)!}{m!n!}.
为简化记号，下令
N_d = \lfloor N/d\rfloor,~M_d=\lfloor M/d\rfloor.
首先，处理分子：(不妨设 N\le M)
\begin{aligned}
F_1(M,N)
&= \sum_{m=1}^M\sum_{n=1}^N[m\perp n]\log_g(m+n-1)!\\
&= \sum_d\mu(d)\sum_{m=1}^{M_d}\sum_{n=1}^{N_d}\log_g((m+n)d-1)!\\
&= \sum_d\mu(d)\Bigg(\sum_{s=2}^{N_d}(s-1)+\sum_{N_d+1}^{M_d}{N_d}+\sum_{M_d+1}^{M_d+N_d}(M_d+N_d+1-s)\Bigg)\log_g(sd-1)!.
\end{aligned}
最后一步就是取 s=m+n，然后计算每个 s 分别对应的数对 (m,n) 的数目。再令
\begin{aligned}
G_0(S,d) &= \sum_{s=1}^S\log_g(sd-1)!,\\
G_1(S,d) &= \sum_{s=1}^S(s-1)\log_g(sd-1)!,
\end{aligned}
就有
\begin{aligned}
F_1(M,N)
&= \sum_d\mu(d)\Bigg(G_1(N_d,d)+N_d(G_0(M_d,d)-G_0(N_d,d)) \\
&\quad\quad\quad\quad\quad+(M_d+N_d)(G_0(M_d+N_d,d)-G_0(M_d,d))\\
&\quad\quad\quad\quad\quad-(G_1(M_d+N_d,d)-G_1(M_d,d))\Bigg) \\
&=\sum_d\mu(d)\left((M_d+N_d)G_0(M_d+N_d,d)-M_dG_0(M_d,d)-N_dG_0(N_d,d)\right) \\
&\quad+\sum_d\mu(d)\left(G_1(M_d,d)+G_1(N_d,d)-G_1(M_d+N_d,d)\right).
\end{aligned}
所以只需要预处理 G_0(S,d) 和 G_1(S,d)，然后计算 S 固定时它们与 \mu(d) 的乘积对 d 的前缀和就可以做数论分块了。
然后，处理分母：
\begin{aligned}
F_2(M,N)&=\sum_{m=1}^M\sum_{n=1}^N[m\perp n](\log_g m!+\log_g n!)\\
&=\sum_d\mu(d)\left(N_d\sum_{s=1}^{M_d}\log_g(sd)!+M_d\sum_{s=1}^{N_d}\log_g(sd)!\right).
\end{aligned}
为避免预处理更多的二维数列，注意到
\sum_{s=1}^{M_d}\log(sd)! = G_0(M_d,d)+\log_g M_d!+M_d\log_g d.
因而，只需要额外再处理 \mu(d) 和 \mu(d)\log_g d 的前缀和即可。
整理下，就有：
\begin{aligned}
&\sum_d\mu(d)(M_d+N_d)\big(G_0(M_d+N_d,d)-G_0(M_d,d)-G_0(N_d,d)\big)\\
&\quad+\sum_d\mu(d)\big(G_1(M_d+N_d,d)-G_1(M_d,d)-G_1(N_d,d)\big)\\
&\quad+\sum_d\mu(d)\big(M_d\log_gN_d!+N_d\log_gM_d!\big)\\
&\quad+\sum_d\mu(d)2M_dN_d\log_gd.
\end{aligned}
虽然形式看起来很整洁，但是跑得并没有更快。仍需要竭尽所能地卡常。