Description：

求 $\begin{align}\sum_{i=0}^kC_n^i\text{ mod }2333\end{align}$

$1\le testcases\le100000,1\le n,k\le 10^{18}$

Solution：

设 $\begin{align}f(n,k)=\sum_{i=0}^kC_n^i\text{ mod }p\end{align}$

由卢卡斯定理得：

$$\begin{align}原式=\sum_{i=0}^kC_{\lfloor\frac n p\rfloor}^{\lfloor\frac i p\rfloor}\times C_{n\%p}^{i\%p}\end{align}$ $

如果把这个式子写出来，会发现它是由许多大小为 $p$ 的 $i/p$ 相同的块和一个最后不完整的块组成的，也就是说可以把式子化成这样： $$\begin{align}\sum_{w=0}^{\lfloor\frac k p\rfloor-1}\sum_{i=0}^{p-1}C_{\lfloor\frac n p\rfloor}^w\times C_{n\%p}^i+\sum_{i=\lfloor\frac k p\rfloor\times p}^kC_{\lfloor \frac n p\rfloor}^{\lfloor\frac k p\rfloor}\times C_{n\%p}^{i\%p}\end{align}$ $

把 $\begin{align}\sum_{i=0}^{p-1}C_{n\%p}^i\end{align}$ 和 $C_{\lfloor \frac n p\rfloor}^{\lfloor\frac k p\rfloor}$ 提出来，原式就是 $\begin{align}\sum_{i=0}^{p-1} C_{n\%p}^i\times\sum_{w=0}^{\lfloor\frac k p\rfloor-1}C_{\lfloor\frac n p\rfloor}^w+C_{\lfloor \frac n p\rfloor}^{\lfloor\frac k p\rfloor}\times\sum_{i=\lfloor\frac k p\rfloor\times p}^k C_{n\%p}^{i\%p}\end{align}$

而 $\begin{align}\sum_{i=\lfloor\frac k p\rfloor\times p}^k C_{n\%p}^{i\%p}=\sum_{i=0}^{k\%p} C_{n\%p}^{i\%p}\end{align}$

即 $f(n\%p,p-1)\times f(\lfloor\frac n p\rfloor,\lfloor\frac k p\rfloor-1)+C_{\lfloor \frac n p\rfloor}^{\lfloor\frac k p\rfloor}\times f(n\%p,k\%p)$

$n\%p$ 和 $k\%p$ 都小于 $2333$ ，所以预处理 $f(n\%p,p-1)$ 和 $f(n\%p,k\%p)$ ， $f(\lfloor\frac n p\rfloor,\lfloor\frac k p\rfloor-1)$ 递归计算， $C_{\lfloor \frac n p\rfloor}^{\lfloor\frac k p\rfloor}$ 由于 $p$ 是质数直接卢卡斯定理。

预处理 $f$ 的话直接用 $f(n,k)=f(n,k-1)+C_n^k$ 即可。

时间复杂度 $O(T\log_{2333}N)$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

const int P = 2333;

int F[P][P];

int C[P][P];

void init()

{

	C[0][0] = 1;

	for(int i = 1;i < P;++i)

	{

		C[i][0] = 1;

		for(int j = 1;j <= i;++j)

		{

			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;

		}

	}

	for(int i = 0;i < P;++i)F[0][i] = 1;

	for(int i = 1;i < P;++i)

	{

		F[i][0] = 1;

		for(int j = 1;j < P;++j)

		{

			F[i][j] = (F[i][j - 1] + C[i][j]) % P;

		}

	}

	return;

}

typedef long long ll;

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int c(ll n,ll m)

{

	if(n < P && m < P)return C[n][m];

	if(n == m)return 1;

	if(m == 0)return 1;

	if(m > n)return 0;

	int res = c(n / P,m / P) * C[n % P][m % P] % P;

	return res; 

}

int f(ll n,ll k)

{

	if(k < 0)return 0;

	if(n == 0 || k == 0)return 1;

	if(n < P && k < P)return F[n][k];

	return ((F[n % P][P - 1] * f(n / P,k / P - 1) % P) + (c(n / P,k / P) * F[n % P][k % P] % P)) % P;

}

void work()

{

	int testcases;

	scanf("%d",&testcases);

	ll n,k;

	for(int i = 1;i <= testcases;++i)

	{

		n = read();k = read();

		printf("%d\n",f(n,k));

	}

	return;

}

int main()

{

	init();

	work();

	return 0;

}