BZOJ4591 [SHOI2015]超能粒子炮·改 [数学]

题目

bzoj4591
luogu4345

$t \ (t \leqslant 1e5)$ 组询问,每次给定两个数 $n、k \ (n、k \leqslant 1e18)$,求

分析

emmmm……和bzoj2154那篇题解一样的命运

但是不知道为什么这个 PDF 显示的 $\LaTeX$ 这么粗 ( 好丑 ),勉强看一下 毕竟实在懒得再打了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

namespace TYC
{
const int p=2333,N=2350;
typedef long long ll;
int C[N][N],f[N][N];

inline ll read()
{
ll x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}

inline int Mod(int x) {return x>=p?x-p:x;}

inline void init()
{
C[0][0]=1;
for(int i=1;i<p;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=Mod(C[i-1][j-1]+C[i-1][j]);
}
for(int i=0;i<p;i++)
for(int j=0;j<p;j++)
f[i][j]=Mod(f[i][j-1]+C[i][j]);
}

inline int Lucas(ll n,ll m)
{
if(!m) return 1;
if(n<m) return 0;
return C[n%p][m%p]*Lucas(n/p,m/p)%p;
}

inline int F(ll n,ll k)
{
if(!k||!k) return 1;
if(n<p&&k<p) return f[n][k];
return Mod(f[n%p][p-1]*F(n/p,k/p-1)%p+Lucas(n/p,k/p)*f[n%p][k%p]%p);
}

void work()
{
init();
int T=read();
while(T--)
{
ll n=read(),k=read();
printf("%d\n",F(n,k));
}
}
}

int main()
{
TYC::work();
return 0;
}