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

 

Leave a Reply

Your email address will not be published. Required fields are marked *