1313. 超能粒子炮・改

参考博客

【洛谷P4345】超能粒子炮·改 - stoorz - 博客园 (cnblogs.com)

题目

1313. 超能粒子炮・改 - AcWing题库 曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。

超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。

它有两个参数 $n,k$，它会向每个编号为 $0$ 到 $k$（包含两端）的位置 $i$ 发射威力为 $C_n^i\mathrm{mod}2333$ 的粒子流。

现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和模 $2333$ 的值。

输入格式

第一行一个整数 $t$ 表示数据组数。

之后 $t$ 行，每行两个整数 $n,k$，含义如题面描述。

输出格式

共 $t$ 行，每行一个整数，表示其粒子流的威力之和模 $2333$ 的值。

数据范围

$1\le t\le 10^5$,
$1\le k\le n\le 10^{18}$

输入样例：

3
5 5
10 7
1145 14

输出样例：

32
968
763

思路

在 $n,k<10^{18}$ 的范围下, 求 $\sum _{i=0}^k{C}_n^i\mathrm{mod}2333$ 的值。

在这个数据范围下能求组合数的方法可以用 $lucas$ 定理：$C_n^m=C_{\frac{n}{p}}^{\frac{m}{p}}\times C_{n\mathrm{mod}p}^{m\mathrm{mod}p}$ 一直递归处理到 $n<p$ 且 $m<p$ 就能直接求得答案。

接下来考虑如何解决求和, 显然无法直接枚举求和, 前缀和的话 $n<10^{18}$ 也不好处理, 只能考虑推导公式了。

设所求函数为 $f(n,k)=\sum _{i=0}^k{C}_n^i\mathrm{mod}p=\sum _{i=0}^k{C}_{\frac{n}{p}}^{\frac{i}{p}}\times C_{n\mathrm{mod}p}^{i\mathrm{mod}p}$, 可以进行如下转换：

\begin{array} &=& (\sum_{i=0}^{p-1}\limits{C_{i}^{\frac{n}{p}}} \times \sum_{i=0}^{\frac{k}{p}-1}\limits{C_{i}^{\frac{n}{p}}})+C_{\frac{n}{p}}^{\frac{k}{p}}\times (\sum_{i=0}^{k\mod p}\limits{C_{i}^{n\mod p}}) \\ =& dad \end{array}

代码