专栏文章

题解：P7890 「MCOI-06」Lost Desire

ccforrest
P7890题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq6zv4d
此快照首次捕获于
2025/12/03 23:59
3 个月前
此快照最后确认于
2025/12/03 23:59
3 个月前
查看原文
提供另一种推式子的方法。
如同其他题解解释的那样，求出原根 gg 后，问题转化为计算离散对数
K∑m=1M∑n=1N[m⊥n]log⁡g(m+n−1)!m!n!.K\sum_{m=1}^M\sum_{n=1}^N[m\perp n]\log_g\dfrac{(m+n-1)!}{m!n!}.
为简化记号，下令
Nd=⌊N/d⌋, Md=⌊M/d⌋.N_d = \lfloor N/d\rfloor,~M_d=\lfloor M/d\rfloor.
首先，处理分子：(不妨设 N≤MN\le M)
F1(M,N)=∑m=1M∑n=1N[m⊥n]log⁡g(m+n−1)!=∑dμ(d)∑m=1Md∑n=1Ndlog⁡g((m+n)d−1)!=∑dμ(d)(∑s=2Nd(s−1)+∑Nd+1MdNd+∑Md+1Md+Nd(Md+Nd+1−s))log⁡g(sd−1)!.\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+ns=m+n，然后计算每个 ss 分别对应的数对 (m,n)(m,n) 的数目。再令
G0(S,d)=∑s=1Slog⁡g(sd−1)!,G1(S,d)=∑s=1S(s−1)log⁡g(sd−1)!,\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}
就有
F1(M,N)=∑dμ(d)(G1(Nd,d)+Nd(G0(Md,d)−G0(Nd,d))+(Md+Nd)(G0(Md+Nd,d)−G0(Md,d))−(G1(Md+Nd,d)−G1(Md,d)))=∑dμ(d)((Md+Nd)G0(Md+Nd,d)−MdG0(Md,d)−NdG0(Nd,d))+∑dμ(d)(G1(Md,d)+G1(Nd,d)−G1(Md+Nd,d)).\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}
所以只需要预处理 G0(S,d)G_0(S,d) 和 G1(S,d)G_1(S,d)，然后计算 SS 固定时它们与 μ(d)\mu(d) 的乘积对 dd 的前缀和就可以做数论分块了。
然后，处理分母：
F2(M,N)=∑m=1M∑n=1N[m⊥n](log⁡gm!+log⁡gn!)=∑dμ(d)(Nd∑s=1Mdlog⁡g(sd)!+Md∑s=1Ndlog⁡g(sd)!).\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}
为避免预处理更多的二维数列，注意到
∑s=1Mdlog⁡(sd)!=G0(Md,d)+log⁡gMd!+Mdlog⁡gd.\sum_{s=1}^{M_d}\log(sd)! = G_0(M_d,d)+\log_g M_d!+M_d\log_g d.
因而，只需要额外再处理 μ(d)\mu(d) 和 μ(d)log⁡gd\mu(d)\log_g d 的前缀和即可。
整理下，就有：
∑dμ(d)(Md+Nd)(G0(Md+Nd,d)−G0(Md,d)−G0(Nd,d))+∑dμ(d)(G1(Md+Nd,d)−G1(Md,d)−G1(Nd,d))+∑dμ(d)(Mdlog⁡gNd!+Ndlog⁡gMd!)+∑dμ(d)2MdNdlog⁡gd.\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}
虽然形式看起来很整洁，但是跑得并没有更快。仍需要竭尽所能地卡常。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...