「SHOI2015」超能粒子炮・改

给你\(T\)组询问，每组询问给定参数\(n,k\)，计算\(\sum\limits_{i=0}^k\dbinom{n}{i}\).

\(T\leq10^5,n,k\leq10^{18}\).

这题其实是\(\operatorname{Lucas}\)定理的一个简单扩展。

首先利用\(\operatorname{Lucas}\)定理化简所求和式，由\(\dbinom{n}{m}=\dbinom{n/p}{m/p}\times\dbinom{n\%p}{m\%p}\pmod p\)得：

\[\begin{align*}
\sum_{i=0}^{k}\binom{n}{i}&=
\sum_{i=0}^k\binom{n/p}{i/p}\binom{n\%p}{i\%p}\\
&=\sum_{i=0}^{p-1}\binom{n\%p}{i}\sum_{j=0}^{k/p-1}\binom{n/p}{j}+\binom{n/p}{k/p}\sum_{i=0}^{k\%p}\binom{n\%p}{i}
\end{align*}
\]

在该和式中，\(\sum\limits_{i=0}^{p-1}\dbinom{n\%p}{i}\)和 \(\sum\limits_{i=0}^{k\%p}\dbinom{n\%p}{i}\)都可以用\(\Omicron(p^2)\)的时间复杂度预处理，而\(\dbinom{n/p}{k/p}\)可以利用\(\operatorname{Lucas}\)定理在\(\Omicron(\log_pn)\)的时间复杂度内计算。

所以我们只要能够计算出\(\sum\limits_{i=0}^{k/p-1}\dbinom{n/p}{i}\)就可以快速计算出\(\sum\limits_{i=0}^{k}\dbinom{n}{i}\)，而这两个式子形式相同，并且每次\(n,k\)规模减半，所以可以递归解决，并且次数不超过\(\log n\)次。

所以总时间复杂度为\(\Omicron(T\log^2n)\).

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=2333;

int T,c[mod+5][mod+5],pre[mod+5][mod+5];

inline ll read(){

    ll res=0,f_f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f_f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch-'0'),ch=getchar();

    return res*f_f;

}

inline void Gmo(int &x){

    while(x<0) x+=mod;

    while(x>=mod) x-=mod;

}

inline void init(){

    c[0][0]=1;

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

        c[i][0]=1;

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

            c[i][j]=c[i-1][j-1]+c[i-1][j];

            Gmo(c[i][j]);

        }

    }

    for (int i=0;i<mod;i++){

        pre[i][0]=c[i][0];

        for (int j=1;j<mod;j++){

            pre[i][j]=pre[i][j-1]+c[i][j];

            Gmo(pre[i][j]);

        }

    }

}

inline int Lucas(ll n,ll m,int p){

    if(m==0) return 1;

    return 1ll*c[n%p][m%p]*Lucas(n/p,m/p,p)%p;

}

inline int calc(ll n,ll k,int p){

    int x=1ll*Lucas(n/p,k/p,p)*pre[n%p][k%p]%mod;

    if(k<p) return x;

    int y=1ll*calc(n/p,k/p-1,p)*pre[n%p][p-1]%mod;

    return (x+y)%mod;

}

int main(){

    T=read(),init();

    while(T--){

        ll x=read(),y=read();

        printf("%d\n",calc(x,y,mod));

    }

    return 0;

}

巴特西

「SHOI2015」超能粒子炮・改

「SHOI2015」超能粒子炮・改

最新文章

热门文章