Luogu4345 SHOI2015 超能粒子炮·改 Lucas、数位DP

模数小，还是个质数，Lucas没得跑

考虑Lucas的实质。设\(a = \sum\limits_{i=0}^5 a_i 2333^i\)，\(b = \sum\limits_{i=0}^5 b_i2333^i\)，那么\(C_a^b \mod2333 = \prod\limits_{i=0}^5 C_{a_i}^{b_i} \mod 2333\)

可以认为Lucas就是将\(a,b\)两个数化成\(2333\)进制数之后每一位组合运算的乘积。似乎与数位相关，使用类似于数位DP的思考方式，从高到低填数。

因为现在需要求的是\(\sum\limits_{i=0}^k C_n^i\)，假设\(k\)在\(2333\)进制下表示为\(\overline {k_5k_4k_3k_2k_1k_0}\)，\(n\)在\(2333\)进制下表示为\(\overline{n_5n_4n_3n_2n_1n_0}\)，那么对于第\(5\)位\(< k_5\)的数，后面的四位一定会取到\(0\)到\(2332\)的所有值。我们处理出\(\prod \limits _{i=0}^4 \sum\limits_{j=0}^{2332} C_{n_i}^j\)，根据二项式定理这其实就是\(2^{n_0+n_1+n_2+n_3+n_4}\)，那么\(2333\)进制下第\(5\)位\(<k_5\)的所有数的贡献就是\(2^{n_0+n_1+n_2+n_3+n_4}\sum\limits_{i=0}^{k_5-1}C_{n_5}^i\)。

最后考虑第\(5\)位等于\(k_5\)的情况，在这种情况下接着考虑第\(4\)位，方式跟上面一致，不断做下去直到所有位都被考虑完。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<ctime>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<iomanip>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<vector>

#include<cmath>

#define ll long long

//This code is written by Itst

using namespace std;

inline ll read(){

    ll a = 0;

    char c = getchar();

    bool f = 0;

    while(!isdigit(c) && c != EOF){

        if(c == '-')

            f = 1;

        c = getchar();

    }

    if(c == EOF)

        exit(0);

    while(isdigit(c)){

        a = a * 10 + c - 48;

        c = getchar();

    }

    return f ? -a : a;

}

const int MOD = 2333;

int C[MOD][MOD] , inv[MOD] , sum[6] , mod[6];

ll powM[6];

inline int poww(int a , int b){

    int times = 1;

    while(b){

        if(b & 1)

            times = times * a % MOD;

        a = a * a % MOD;

        b >>= 1;

    }

    return times;

}

int calc(ll cur , int now){

    if(now < 0)

        return 1;

    if(cur / powM[now])

        return (C[mod[now]][cur / powM[now] - 1] * sum[now] + (C[mod[now]][cur / powM[now]] - C[mod[now]][cur / powM[now] - 1] + MOD) * calc(cur % powM[now] , now - 1)) % MOD;

    return calc(cur , now - 1);

}

void init(){

    powM[0] = sum[0] = 1;

    for(int i = 1 ; i <= 5 ; ++i)

        powM[i] = powM[i - 1] * MOD;

    C[0][0] = 1;

    for(int i = 1 ; i < MOD ; ++i){

        C[i][0] = 1;

        for(int j = 1 ; j < MOD ; ++j)

            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

    }

    for(int i = 0 ; i < MOD ; ++i)

        for(int j = 1 ; j < MOD ; ++j)

            C[i][j] = (C[i][j] + C[i][j - 1]) % MOD;

}

signed main(){

#ifndef ONLINE_JUDGE

    freopen("in","r",stdin);

    freopen("out","w",stdout);

#endif

    init();

    for(int T = read() ; T ; --T){

        ll N = read() , K = read();

        for(int i = 1 ; i <= 5 ; ++i){

            mod[i - 1] = N / powM[i - 1] % 2333;

            sum[i] = poww(2 , mod[i - 1]) * sum[i - 1] % MOD;

        }

        mod[5] = N / powM[5];

        cout << calc(K , 5) << '\n';

    }

    return 0;

}

巴特西

Luogu4345 SHOI2015 超能粒子炮·改 Lucas、数位DP

最新文章

热门文章