某道XJ题

题意

经过打表找规律和题意转化后，题意如下：

假定\(p \leq 2 * {10} ^ 5, q \leq 10 ^ 9, F(n) = \prod_{i = 1} ^ n (q ^ i - 1)\)，且\(p, q \in \mathbb{P}\)，求\(\frac{F(n + m)}{F(n) F(m)} \bmod p\)。

题解

令\(r\)为\(q\)在\(\bmod p\)下的阶，则

\[
q ^ r \equiv 1 \bmod p \\q ^ r - 1 \equiv 0 \bmod p \\
\]

\[
\begin{aligned}F(n)& = \prod_{i = 1} ^ n (q ^ i - 1) \\& \equiv \left(\prod_{i = 1} ^ {r} (q ^ i - 1)\right) ^ {\lfloor \frac{n}{r} \rfloor} \left(\prod_{i = 1} ^ {n \bmod r} (q ^ i - 1) \right) \bmod p \\ & \equiv \left(\prod_{i = 1} ^ {r - 1} (q ^ i - 1)\right) ^ {\lfloor \frac{n}{r} \rfloor} \left(\prod_{i = 1} ^ {n \bmod r} (q ^ i - 1) \right) \left(\prod_{i = 1} ^ {\lfloor \frac{n}{r} \rfloor} (q ^ {ir} - 1) \right) \bmod p \\ \end{aligned}
\]

对于\(\frac{F(n + m)}{F(n)F(m)}\)，主要问题是处理\(\prod (q ^ {ir} - 1)\)的部分（其他部分都有逆元，较容易，需要预处理的部分在\(\mathcal O(p)\)的时间就可以完成）。

令\(G(n) = \prod_{i = 1} ^ {\lfloor \frac{n}{r} \rfloor} (q ^ {ir} - 1)\)，则

\[
\begin{aligned}G(n)& = \prod_{i = 1} ^ {\lfloor \frac{n}{r} \rfloor} (q ^ r - 1)(q ^ {(i - 1)r} + q ^ {(i - 2)r} + \ldots + 1) \\& \equiv \prod_{i = 1} ^ {\lfloor \frac{n}{r} \rfloor} (q ^ r - 1)(1 + 1 + \ldots + 1) \bmod p \\& \equiv \prod_{i = 1} ^ {\lfloor \frac{n}{r} \rfloor} (q ^ r - 1) \cdot i \bmod p \\& \equiv (q ^ r - 1) ^ {\lfloor \frac{n}{r} \rfloor} \left({\lfloor \frac{n}{r} \rfloor} \right)! \bmod p \\\end{aligned}
\]

则涉及到的部分\(\frac{G(n + m)}{G(n) G(m)}\)即为

\[
\begin{aligned}& \frac{(q ^ r - 1) ^ {\lfloor \frac{n + m}{r} \rfloor} \left({\lfloor \frac{n + m}{r} \rfloor}\right)!}{(q ^ r - 1) ^ {\lfloor \frac{n}{r} \rfloor} \left({\lfloor \frac{n}{r} \rfloor}\right)! (q ^ r - 1) ^ {\lfloor \frac{m}{r} \rfloor} \left({\lfloor \frac{m}{r} \rfloor}\right)!} \bmod p \\\equiv & \frac{(q ^ r - 1) ^ {\lfloor \frac{n + m}{r} \rfloor} \left({\lfloor \frac{n + m}{r} \rfloor}\right)!}{(q ^ r - 1) ^ {\lfloor \frac{n}{r} \rfloor + \lfloor \frac{m}{r} \rfloor} \left({\lfloor \frac{n}{r} \rfloor}\right)! \left({\lfloor \frac{m}{r} \rfloor}\right)!} \bmod p \\\end{aligned}
\]

易见，当且仅当\(\lfloor \frac{n + m}{r} \rfloor = \lfloor \frac{n}{r} \rfloor + \lfloor \frac{m}{r} \rfloor\)的时候，上式不为0。

否则，包含\((q ^ r - 1)\)的部分全部消去，剩下的是一个组合数的计算，是个经典问题，可以用lucas定理\(\mathcal O(\log n)\)递归处理。

总复杂度\(\mathcal O(p + T \log n)\)。