题目描述

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

超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数 n , k ，它会向每个编号为 0 到 k （包含两端）的位置 i发射威力为Cni ​mod2333 的粒子流。

现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和除以 2333 所得的余数。

输入输出格式

输入格式：

第一行一个整数 t表示数据组数。 之后 t行，每行两个整数 n、 k ，含义如题面描述。

输出格式：

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

思路：

我们先看一下样例（p=5，k=10，m=13）

   13 0 1 2 3 4 5 6 7 8 9 10

1  3  0 1 2 3 4 0 1 2 3 4 0

5  2  0 0 0 0 0 1 1 1 1 1 2

我们可以惊奇的发现，这是可以用lucas合并的

为什么呢？

这么多重复的（00000）（11111）

明显可以合并加速

那怎么合并呢？

我们可以通过预处理组合数的办法（p只有2333），提前求出组合数c

再求出组合数前缀和S

然后递推公式是这个：

S(n,k)mod p=[S(n/p,k/p-1)*S(n mod p,p-1)+C(n/p,k/p)*S(n mod p,k mod p)]mod p

再套回去，就出来了

Code：

#include
     
      #include
      
       #define rii register int i#define rij register int j#define rit register int t#define ll long longusing namespace std;long long i,j,k,m,n,x,y,z,p=2333,q;long long c[2335][2335],s[2335][2335];int C(ll x,ll y){    return (x
       
        >q;    for(rit=1;t<=q;t++)    {        scanf("%ld",&n);        scanf("%ld",&k);        printf("%ld\n",S(n,k));    }}