Article From:https://www.cnblogs.com/CzxingcHen/p/9686011.html

BZOJ4591

Combinatorial mathematics that can not be written.

If we set $f (n, K) = \sum_{i= 0}^{k}\binom{n}{i}$, then each request is $f (n, K)$.

It turns out that $f (I, J)$can be recursively:

$f(i, 0) = 1$

$f(i, j) = f(i, j – 1) + \binom{i}{j}$

It doesn’t seem to be useful, but we also have the $Lucas$theorem.

$f(n, k) = \sum_{i = 0}^{k}\binom{n}{i} \ (Mod\ P) \ =\sum_{i = 0}^{k}\binom{\left \lfloor \frac{n}{P} \right \rfloor}{\left \lfloor \frac{i}{P} \right \rfloor} * \binom{n\%p}{i\%p}$

See the $left lfloor frac {i} P right rfloor$stuff, and we know that it has only $sqrt {P} values, so we’re putting the same stuff forward, and we’re putting it all together$\ lefT lfloor frac {k}{P} righ t rfloor – 1 $complete loop section, and an incomplete loop section is$ binom {\ left lfloor\ frac {n} {P}\ righT \rfloor}{\left \lfloor \frac{k}{P} \right \rfloor}\sum_{i = 0}^{k /% P}\binom{n\% P}{i}$. Add up:$\sum_{i = 0}^{\left \lfloor \frac{k}{p} \right \rfloor – 1}\binom{\left \lfloor \frac{n}{P} \right \rfloor}{i}\sum_{j = 0}^{P – 1}\binom{n \% P}{j} + \binom{\left \lfloor \frac{n}{P} \right \rfloor}{\left \lfloor \frac{k}{P} \right \rfloor}\sum_{i = 0}^{k \% P}\binom{n\% P}{i}$The discovery is actually a superposition of several sub problems.$f(\left \lfloor \frac{n}{P} \right \rfloor , \left \lfloor \frac{k}{P} \right \rfloor – 1)* f(n \% P , P – 1) + f(n \% P , k \% P) * \binom{\left \lfloor \frac{n}{P} \right \rfloor}{\left \lfloor \frac{k}{P} \right \rfloor}$So for all the$f $, we can directly recursively solve it, less than the modulus of$f $can be directly recursive preprocessing, you can find that the recursive depth must not exceed the$log $layer, there is a combination number, with the$Lucas $theorem to calculate a wave. The time complexity is$O (P^2 + Tlogn) $, and the base of$log$is$2333\$.

Code：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 2505;
const int P = 2333;

int testCase, c[N][N], f[N][N];

inline int lucas(ll n, ll m) {
if(m == 0LL) return 1;
if(n < P && m < P) return c[n][m];
return lucas(n / P, m / P) * c[n % P][m % P] % P;
}

inline int solve(ll n, ll k) {
if(k == -1LL) return 0;
if(n < P && k < P) return f[n][k];
return (solve(n / P, k / P - 1) * solve(n % P, P - 1) % P + lucas(n / P, k / P) * solve(n % P, k % P) % P) % P;
}

int main() {
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] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
}

for(int i = 0; i <= P; i++) {
f[i][0] = 1;
for(int j = 1; j <= P; j++)
f[i][j] = (f[i][j - 1] + c[i][j]) % P;
}

for(scanf("%d", &testCase); testCase--; ) {
ll n, K; scanf("%lld%lld", &n, &K);
printf("%d\n", solve(n, K));
}

return 0;
}

View Code