description
求 \(\sum\limits_{i=0}^k \dbinom{n}{i} \bmod 2333\)
2333 是质数。
\(10^5\) 测，\(n,k\leq 10^{18}\)。
solution
由 Lucas 定理，\(\dbinom{n}{m}\equiv \dbinom{n\bmod p}{m\bmod p}\dbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor} \pmod p\)，要求 \(p\) 是质数。
因此我们可以按数位来 dp。
记 \(pos_i(n)\) 表示 \(n\) 在 2333 进制下从小到大第 \(i\) 位的数值。
设 \(f_i\) 表示 \(\sum\limits_{j=0}^{2333^{i}-1}\dbinom{n}{i}\)。
则有转移式：
- \(f_0=1\)
- \(f_m=\sum\limits_{i=0}^{2333-1}\dbinom{pos_m(n)}{i}\times f_{m-1}\)。（即枚举最高位是多少）。
设 \(h_i\) 表示对于 \((n,k\bmod 2333^i)\) 的答案，则有
-
\(h_0=\sum\limits_{i=0}^{k\bmod 2333} \dbinom{n\bmod 2333}{i}\)
-
\(h_i=\dbinom{pos_i(n)}{pos_i(k)}h_{i-1}+\sum\limits_{j=0}^{pos_i(k)-1}\dbinom{pos_i(n)}{j}\times f_{i-1}\)
一组询问的答案就是 \(h_{\log_p^{\max(n,k)}}\)
预处理组合数及其每行的前缀和，每次询问 dp 后回答即可。
时间复杂度 \(O(p^2+T\log_{p} n)\)，其中 \(p=2333\)。