洛谷P4345 超能粒子炮·改

超能粒子炮·改"/>

洛谷P4345 超能粒子炮·改

传送门

题目描述

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

超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数 n,kn,k ，它会向每个编号为 00 到 kk （包含两端）的位置 ii 发射威力为 C_{n}^{i} \bmod 2333C
n
i
​
mod2333 的粒子流。

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

输入格式

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

之后 tt 行，每行两个整数 n,kn,k，含义如题面描述。

输出格式

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

输入输出样例
输入 #1复制
3
5 5
10 7
1145 14
输出 #1复制
32
968
763

说明/提示

对于 10%10% 的数据，t = 1,n,k \le 1000t=1,n,k≤1000 ；
对于 30%30% 的数据，t = 1,n,k \le 1000000t=1,n,k≤1000000 ；
对于 50%50% 的数据，t = 1,n \le 10^{18},k \le 1000t=1,n≤10
18
,k≤1000 ；
对于 70%70% 的数据，t = 100,n,k \le 10^{18}t=100,n,k≤10
18
；
对于 100%100% 的数据，t = 100000,n,k \le 10^{{18}t=100000,n,k≤10}18

上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int p = 2333;
LL t,a,b,c[2550][2550],f[2550][2550];
inline LL read()
{LL s = 0, w = 1; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}return s * w;
}
LL Lucas(LL n, LL m)//Lucas定理求组合数
{if(m == 0) return 1;if(n < m) return 0;return c[n%p][m%p] * Lucas(n/p,m/p) % p;
}
LL calc(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] * calc(n/p,k/p-1) % p + Lucas(n/p,k/p) * f[n%p][k%p] % p) % p;//递归处理
}
void YYCH()//预处理出0-p的组合数
{c[0][0] = f[0][0] = 1;for(int i = 1; i <= 2500; i++)//杨辉三角求组合数{c[i][0] = c[i][i] = 1;for(int j = 0; j <= i; j++){c[i][j] = (c[i-1][j-1] + c[i-1][j]) % p;}}	for(int i = 0; i <= 2500; i++) f[i][0] = 1;for(int i = 0; i <= 2500; i++)//组合数的前缀和{for(int j = 1; j <= 2500; j++){f[i][j] = (f[i][j-1] + c[i][j]) % p;}}
}
int main()
{t = read(); YYCH();while(t--){a = read(); b = read();printf("%lld\n",calc(a,b));}return 0;
}