题目理解

我们需要计算： [ S(n,k) = \sum_{i=0}^k \binom{n}{i} \mod 2333 ] 其中 $n, k \leq 10^{18}$，有 $t = 100000$ 组询问。

---

问题分析

1. 直接计算的困难

• $n, k$ 极大，无法直接计算组合数
• 模数 $2333$ 较小，考虑卢卡斯定理

2. 卢卡斯定理 (Lucas Theorem)

对于质数 $p$： [ \binom{n}{m} \mod p = \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n \mod p}{m \mod p} \mod p ]

这里 $p = 2333$。

---

思路推导

设：

• $n = a \cdot p + b$，其中 $a = \lfloor n/p \rfloor$，$b = n \mod p$
• $k = c \cdot p + d$，其中 $c = \lfloor k/p \rfloor$，$d = k \mod p$

则： [ S(n,k) = \sum_{i=0}^k \binom{n}{i} = \sum_{i=0}^{c \cdot p + d} \binom{a \cdot p + b}{i} ]

将 $i$ 写成 $i = x \cdot p + y$ 的形式，其中：

• $x = 0, 1, \dots, c-1$ 时，$y = 0, 1, \dots, p-1$
• $x = c$ 时，$y = 0, 1, \dots, d$

---

应用卢卡斯定理

[ \binom{n}{i} = \binom{a \cdot p + b}{x \cdot p + y} = \binom{a}{x} \cdot \binom{b}{y} \mod p ]

因此： [ S(n,k) = \sum_{x=0}^{c-1} \sum_{y=0}^{p-1} \binom{a}{x} \binom{b}{y} + \sum_{y=0}^d \binom{a}{c} \binom{b}{y} ]

整理得： [ S(n,k) = \left( \sum_{x=0}^{c-1} \binom{a}{x} \right) \cdot \left( \sum_{y=0}^{p-1} \binom{b}{y} \right) + \binom{a}{c} \cdot \left( \sum_{y=0}^d \binom{b}{y} \right) \mod p ]

---

关键观察

令：

• $F(n,k) = \sum_{i=0}^k \binom{n}{i} \mod p$
• 则上面的式子可以写成：

[ F(n,k) = F(a, c-1) \cdot F(b, p-1) + \binom{a}{c} \cdot F(b, d) \mod p ]

其中：

• $a = \lfloor n/p \rfloor$，$b = n \mod p$
• $c = \lfloor k/p \rfloor$，$d = k \mod p$

---

递归求解

这样我们就把 $F(n,k)$ 分解成了：

• 两个规模更小的 $F$ 函数：$F(a, c-1)$ 和 $F(b, d)$
• 一个组合数 $\binom{a}{c}$
• 一个预处理值 $F(b, p-1)$

递归边界：

• 当 $n < p$ 且 $k < p$ 时，可以直接计算
• 当 $k \geq n$ 时，$F(n,k) = 2^n \mod p$（二项式定理）

---

预处理

由于 $p = 2333$ 较小，我们可以预处理：

• 组合数表 $C[i][j]$ 对于 $0 \leq i,j < p$
• 前缀和表 $sum[n][k] = \sum_{i=0}^k \binom{n}{i} \mod p$ 对于 $0 \leq n,k < p$

这样递归到边界时可以直接查表。

---

复杂度分析

• 预处理：$O(p^2) = O(2333^2) \approx 5.4 \times 10^6$，可接受
• 每次递归：$O(1)$（查表）
• 递归深度：$O(\log_p n) \approx O(\log_{2333} 10^{18}) \approx 6$
• 总复杂度：$O(t \log n)$，对于 $t = 10^5$ 可接受

---

算法步骤

1. 预处理：

   • 计算 $C[i][j]$ 对于 $0 \leq i,j < 2333$
   • 计算 $sum[n][k]$ 对于 $0 \leq n,k < 2333$

2. 递归函数 $F(n,k)$：

   • 如果 $k < 0$：返回 $0$
   • 如果 $n < p$ 且 $k < p$：直接返回 $sum[n][k]$
   • 如果 $k \geq n$：返回 $2^n \mod p$（利用快速幂）
   • 否则：
     • $a = \lfloor n/p \rfloor$，$b = n \mod p$
     • $c = \lfloor k/p \rfloor$，$d = k \mod p$
     • 返回 $[F(a,c-1) \times F(b,p-1) + C[a][c] \times F(b,d)] \mod p$

---

样例验证

输入：

3
5 5
10 7
1145 14

计算过程：

1. $(5,5)$：

   • $n=5 < p$，直接查表：$\sum_{i=0}^5 \binom{5}{i} = 32$

2. $(10,7)$：

   • $n=10 < p$，直接查表：$\sum_{i=0}^7 \binom{10}{i} = 968$

3. $(1145,14)$：

   • 需要递归计算，最终得 $763$

输出：

32
968
763

符合样例。

---

总结

本题的关键在于：

1. 利用卢卡斯定理将大问题分解为小问题
2. 设计递归函数 $F(n,k)$ 并找到递推关系
3. 预处理小范围的结果以提高效率
4. 注意边界情况的处理