Luogu

BZOJ

分析

$\mathrm{Lucas}$ 定理+推式子。

题目要求的是 $\sum\limits_{i=0}^kC_n^i\%p$ 。

设 $f(n,k)=\sum\limits_{i=0}^kC_n^i\%p$ ，进一步得到 $f(n,k)=\sum\limits_{i=0}^kC_{n/p}^{i/p}*C_{n\%p}^{i\%p}$ 。

$i/p$ 可以数论分块一波，得到 $C_{n/p}^0\sum\limits_{i=0}^{p-1}C_{n\%p}^i+C_{n/p}^1\sum\limits_{i=0}^{p-1}C_{n\%p}^i+...+C_{n/p}^{k/p}\sum\limits_{i=0}^{k\%p}C_{n\%p}^i$ 。

把 $\sum\limits_{i=0}^{p-1}C_{n\%p}^i$ 单独提出来，得到 $C_{n/p}^{k/p}\sum\limits_{i=0}^{k\%p}C_{n\%p}^i+\sum\limits_{i=0}^{p-1}C_{n\%p}^i*(C_{n/p}^0+C_{n/p}^1+...+C_{n/p}^{k/p-1})$ 。

再进一步得到 $f(n\%p,p-1)*f(n/p,k/p-1)+C_{n/p}^{k/p}*f(n\%p,k\%p)$ 、

于是递归计算即可。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2500;
const int mod=2333;

int C[N][N],sum[N][N];

inline void init() {
    C[0][0]=1;
    for (re int i=1;i<N;++i) {
        C[i][0]=1;
        for (re int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    for (re int i=0;i<N;++i) {
        sum[i][0]=1;
        for (re int j=1;j<N;++j)
            sum[i][j]=(sum[i][j-1]+C[i][j])%mod;
    }
}

inline int lucas(int n,int m) {
    if (!m) return 1;
    return 1ll*C[n%mod][m%mod]*lucas(n/mod,m/mod)%mod;
}

inline int f(int n,int k) {
    if (k<0) return 0;
    if (!n||!k) return 1;
    if (n<mod&&k<mod) return sum[n][k];
    return (1ll*f(n/mod,k/mod-1)*sum[n%mod][mod-1]%mod
           +1ll*lucas(n/mod,k/mod)*sum[n%mod][k%mod]%mod)%mod;
}

signed main() {
    init(); int T=read();
    while (T--) {
        int n=read(),k=read();
        printf("%lld\n",f(n,k));
    }
    return 0;
}