问题分析

有 $n$ 所学校，第 $i$ 所学校：

• 学生总数 $c_i$
• 礼堂容量 $x_i$
• 每个礼堂必须坐满（不能有空位）

要求：每个学校选择 $x_i$ 个学生听讲座，问方案数，模 $p$（$p$ 不一定是质数）。

1. 单所学校方案数

对于第 $i$ 所学校，从 $c_i$ 个学生中选 $x_i$ 个，方案数为组合数：

$\binom{c_i}{x_i}$

总方案数为各学校方案数之积：

$\text{Ans} = \prod_{i=1}^n \binom{c_i}{x_i}$

需要计算 $\prod_{i=1}^n \binom{c_i}{x_i} \bmod p$，其中 $p$ 不一定是质数。

2. 难点

普通 Lucas 定理或逆元法要求模数是质数，这里 $p$ 任意，不能直接用逆元。

组合数公式： $\binom{c}{x} = \frac{c!}{x! \cdot (c-x)!}$ 所以： $ \text{Ans} = \frac{\prod_{i=1}^n c_i!}{\prod_{i=1}^n x_i! \cdot \prod_{i=1}^n (c_i - x_i)!} $

问题转化为：计算一个分数的模 $p$ 值，但分母可能与 $p$ 不互素，不能直接求逆元。

3. 质因数分解法

设 $p = \prod_j q_j^{e_j}$ 是 $p$ 的质因数分解。

对每个质因子 $q$，计算 $\text{Ans}$ 中 $q$ 的幂次以及剩余部分：

令 $v_q(m) = m \text{ 中质因子 } q \text{ 的幂次}$ 则 $ v_q\left( \binom{c}{x} \right) = v_q(c!) - v_q(x!) - v_q((c-x)!) $ 用 Legendre 公式： $ v_q(n!) = \left\lfloor \frac{n}{q} \right\rfloor + \left\lfloor \frac{n}{q^2} \right\rfloor + \dots $

对每个质因子 $q$，计算： $ E_q = \sum_{i=1}^n \left[ v_q(c_i!) - v_q(x_i!) - v_q((c_i - x_i)!) \right] $ 如果 $E_q \ge e$（$p$ 中 $q$ 的幂次 $e$），那么最终答案中 $q$ 的幂次至少为 $e$，模 $p$ 为 $0$。

如果对所有 $q$ 都有 $E_q < e$，那么我们可以计算： $A = \prod_{i=1}^n \frac{c_i!}{x_i! (c_i-x_i)!}$ 去掉所有因子 $q$ 后，剩余部分与 $p$ 互素，可以求逆元。

4. 实际计算步骤

1. 对 $p$ 做质因数分解。
2. 对每个质因子 $q$，计算 $E_q$。
3. 如果存在 $q$ 使得 $E_q \ge e$，输出 $0$（因为组合数乘积是 $p$ 的倍数）。
4. 否则，计算： $ N = \prod_{i=1}^n c_i!,\quad D = \prod_{i=1}^n x_i! \cdot \prod_{i=1}^n (c_i-x_i)! $ 但计算时去掉所有质因子 $q$（即只保留与 $p$ 互素的部分）。
5. 计算 $N \times D^{-1} \bmod p$，其中 $D^{-1}$ 是 $D$ 在模 $p$ 下的逆元（因为现在 $D$ 与 $p$ 互素）。

5. 样例验证

输入：

n=2, p=10000000
x = [1, 2]
c = [100, 2000]

计算： $ \binom{100}{1} = 100,\quad \binom{2000}{2} = \frac{2000 \times 1999}{2} = 1999000 $ 乘积： $100 \times 1999000 = 199900000$ 模 $10^7$： $199900000 \bmod 10000000 = 9900000$ 与输出一致。

6. 算法复杂度

• 质因数分解 $p$：$O(\sqrt{p})$，但 $p \le 10^7$ 可行。
• 计算阶乘的质因子幂次：需要预处理或直接计算，但 $c_i$ 可能很大（题目未给范围，但应能接受 $O(\log c_i)$ 计算）。
• 总体可行。

7. 总结

本题的关键是处理模数不一定是质数情况下的组合数乘积。通过质因数分解，分别处理每个质因子的幂次，可以判断是否答案为 $0$，否则去掉公共质因子后利用互质性求逆元。这是一种标准的非质数模数下组合数计算方法。