Eva

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明：超能粒子炮·改--一种可以发射威力更加

强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮，在威力上有了本质的提升。它有三个参数n，k。它会

向编号为0到k的位置发射威力为C(n,k) mod 2333的粒子流。现在SHTSC给出了他的超能粒子炮·改的参数，让你求

其发射的粒子流的威力之和模2333。

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

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

k<=n<=10^18，t<=10^5

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

1
5 5

32

/**************************************************************

    Problem: 4591

    User: ictsing

    Language: C++

    Result: Accepted

    Time:3980 ms

    Memory:50120 kb

****************************************************************/

 

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int mod = 2333;

typedef long long ll;

const int mt = 2500;

int c[mt][mt],sum[mt][mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

inline ll readll()

{

    ll num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int lucas(ll x,ll y)

{

    if(x<y||y<0) return 0;

    if(x<mod&&y<mod) return c[x][y];

    return lucas(x/mod,y/mod)*c[x%mod][y%mod]%mod;

}

int cal(ll n,ll k)

{

    if(k<0) return 0;

    return (cal(n/mod,k/mod-1)*sum[n%mod][mod-1]%mod+lucas(n/mod,k/mod)*sum[n%mod][k%mod]%mod)%mod;

}

int main()

{

    c[0][0]=sum[0][0]=1;

    for(int i=1;i<mod;i++) sum[0][i]=1;

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

    {

        sum[i][0]=c[i][0]=1;

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

            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

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

            sum[i][j]=(sum[i][j-1]+c[i][j])%mod;

    }

    int T_T=read();

    while(T_T--)

    {

        ll n=readll(),k=readll();

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

    }

    return 0;

}