传送门

思路很妙的$Lucas$。

设$f(n,k)=\sum\limits_{i=0}^kC_n^i$

套上卢卡斯：

$f(n,k)=\sum\limits_{i=0}^kC_{n/p}^{i/p}C_{n\% p}^{i\% p}$

$i$每增长$p$，$i/p$才会加$1$。把$C_{n/p}^{i/p}$拆出来：

$=\left(\sum\limits_{i=0}^{k/p-1}C_{n/p}^i\sum\limits_{j=0}^{p-1}C_{n\% p}^{j}\right)+C_{n/p}^{k/p}\sum\limits_{i=0}^{k\% p}C_{n\% p}^{i}$

$=f(n/p,k/p-1)f(n\% p,p-1)+C_{n/p}^{k/p}f(n\% p,k\% p)$

$f$相当于是组合数的前缀和，$O(p^2)$预处理$0\sim p-1$的$f$，递归计算$f(n/p,k/p-1)$，$C_{n/p}^{k/p}$用卢卡斯计算即可。

注意特判递归时$k<0$的情况。

复杂度：$O(t\log_p^2n)$

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 100005
#define inf 0x3f3f3f3f

const int mod = 2333;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int c[mod+1][mod+1],f[mod+1][mod+1];
int C(long long n,long long m){//注意long long
    if(n<m)return 0;
    if(n>=mod)return C(n/mod,m/mod)*C(n%mod,m%mod)%mod;
    return c[n][m];
}
int F(long long n,long long k){
    if(k<0)return 0;
    if(k>=mod||n>=mod)return (f[n%mod][mod-1]*F(n/mod,k/mod-1)%mod+C(n/mod,k/mod)*f[n%mod][k%mod]%mod)%mod;
    return f[n][k];
}
int main(){
    c[0][0]=1;
    for(register int i=0;i<mod;++i)f[0][i]=1;
    for(register int i=1;i<mod;++i){
        c[i][0]=f[i][0]=1;
        for(register int j=1;j<mod;++j)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod,f[i][j]=(f[i][j-1]+c[i][j])%mod;
    }
    int t=read();
    long long n,k;
    while(t--)n=read<long long>(),k=read<long long>(),printf("%d\n",F(n,k));    
}