题解：P10548 [THUPC 2024 决赛] 朔望

· · 题解

0x00 前言

读了半天没读懂白鸽子同学的题解，我自己也来写一篇。

0x01 题目大意

我们从一个初中生的角度理解题目。小奥大家都知道有个东西叫环形跑道，就是一些人在一个环形跑道上行动。这道题是一样的，一些行星在一个长度为 1（这个不是很重要，设一个就好）的跑道上进行运动，已经知道了每个行星运动完一圈所需要花的时间。

继续理解什么是所谓 Syzygy，朔望现象。就是两个行星，之间的距离是 0 或 \frac{1}{2}，就是这个轨道的一侧或间距一半。我们会发现，存在很多种情况，比如只有两颗行星共线，或者三颗，甚至四颗。这时候题目告诉我们这些情况对答案的贡献是不一样的，需要乘上一个整数。在一个周期内（行星运行一圈所需时间的最小公倍数的倍数）把所有“朔望”的贡献加起来，初一这个周期的时刻数量，假设此时的结果是 \frac{p}{q}，答案 ans 可以表示为：

\frac{p}{q} \equiv x \pmod {10^9 + 7}

0x01 题目分析 & 算法设计

不要被各种公式吓懵，这是一道紫题。

0x01 化简求答案的公式

首先我们需要解决这个答案 ans 的求法。这个公式：

\frac{p}{q} \equiv x \pmod {10^9 + 7}

这时候我们利用费马小定理，当 m 是质数且 \gcd(x, m) = 1 时：

b^{-1} \equiv b^{m - 2} \pmod m

因为 10^9 + 7 是质数并且显然 \gcd(q, m) = 1（因为 q 是 t_{1 \dots n} 的最小公倍数的倍数的因数，并且 t_{1 \dots n} 均 \le 10^9，所以 t_{1 \dots n} 的最小公倍数一定没有 10^9 + 7 这个质因子，所以其因数更没有这个质因子，进而与 10^9 + 7 互质），所以：

\frac{p}{q} = p \times q ^ {-1} \equiv p \times q^{10^9 + 7 - 2} = p \times q^{10^9 + 5} \equiv x \pmod {10^9 + 7}

即：

x \equiv p \times q^{10^9 + 5} \pmod {10^9 + 7}

现在我们的问题只在于解决 \frac{p}{q} 了。

0x02 “朔望”怎么计算

我们先考虑简化问题，只考虑两个行星的系统。

设这两个行星的公转周期是 t_1 和 t_2，不妨设 t_1 < t_2。所以运行速度是 v_1 = \frac{1}{t_1} 和 v_2 = \frac{1}{t_2}，此时显然 v_1 > v_2。此时，“朔望”怎么理解，就是我在 “题目大意”部分已经说过的这句话：

继续理解什么是所谓 Syzygy，朔望现象。就是两个行星，之间的距离是 0 或 \frac{1}{2}，就是这个轨道的一侧或间距一半。

所以，考虑一开始两个行星之间的距离是 0，下一次达到 \frac{1}{2} 就是产生 \frac{1}{2} 的路程差，再下一次达到 0 就是再产生 \frac{1}{2} 的路程差。根据 t \times v = s（行程问题的基础），即 t = \frac{s}{v}，所以对于两颗行星，“朔望”周期就是：

\frac{\frac{1}{2}}{v_1 - v_2} = \frac{1}{2(\frac{1}{t_1} + \frac{1}{t_2})} = \frac{t_1t_2}{2(t_2 - t_1)}

继续考虑“三星系统”。是行星，不是恒星，不是三体问题。 在证明三点共线是有一个证法，就是证明 C 在直线 AB 上。这时候我们可以先让行星 1 和 2“朔望”，在计算什么时候 1 与 3“朔望”，然后三星同时“朔望”在周期 T 里面的“朔望”次数就是（不妨设 t_1 < t_2 < t_3）：

\gcd(\frac{T \,\cdot\, 2(t_2 - t_1)}{t_1t_2}, \frac{T \,\cdot\, 2(t_3 - t_1)}{t_1t_3})

另外，对于周期 T，因为影响答案的是概率，所以 T 只要是 t_{1 \dots n} 的最小公倍数的倍数即可。显然当 T = \prod t_i 时满足要求，所以这时候，我们粗略地把 T 看作 \prod t_i。所以显然所有的 \frac{T \,\cdot\, 2(t_j - t_i)}{t_it_j}，满足 t_i < t_j，一定是正整数。

进而，以此类推，对于一个 k 星系统，k 星“朔望”在 T 内的次数就是 \gcd ^ k _{i = 2} \frac{T \,\cdot\, 2(t_i - t_1)}{t_1t_i}，即计算所有 2 \,\sim\, k 中所有与 1“朔望”的周期最小公倍数。

这样，数学部分也就解决了。

0x03 算法设计

观察我们得到的式子，首先先把 2 提出来，然后预处理 \frac{T}{t_1t_i} 和 t_i - t_1 的每一个质因数，因为 \gcd 本质就是质因数的运算。两者乘起来之后可以发现实质上不同的质因数数量很少，所以考虑直接暴力存储并且在以 10^9 + 7 为模数的情况下求解答案。

我们直接选择一些行星，时间复杂度 O(n^2)，设总质因数个数为 p，此时进行数学计算的时间复杂度为 O(n + w)，整体时间复杂度 O(2^n(n + w))。

但是，在我们的算法里面根本没有考虑在当前这个行星中，该内部“朔望”没有更多的集合外的行星也发生了“朔望”。所以，我们需要再使用 IFWT 算法在 O(w2^n) 的时间复杂度内实现该过程，按照前面的公式求取答案即可。

0x04 代码实现

这是一道大模拟，只需要注意一些细节即可。

IFWT 算法：

这里我的讲解比较粗略，直接放代码：

void IFWT(ll *f)
{
    for(int i = 1; i <= n; i++)
    {
        for(int st = tot; st >= 1; st--)
        {
            if(!((st >> (i - 1)) & 1)) continue;
            int nw = st ^ (1 << (i - 1));
            cnts[nw] = (cnts[nw] - cnts[st] + mo) % mo;
        }
    }
}

其他的讲解相对详细，可以直接写出代码，具体代码大家直接参考原题解就好了，只是我认为我的思路更加详细。

0x05 后记

本人水平不高，有问题请在评论区指出。本文对白鸽子同学的题解有大量的参考，但是我认为原题解的讲解不够详细，故又发文解释。

AC 记录。