洛谷 P4345 [SHOI2015]超能粒子炮·改 解题报告

P4345 [SHOI2015]超能粒子炮·改

题意

求(sum_{i=0}^kinom{n}{i})，(T)组数据

范围

(Tle 10^5,n,jle 10^{18})

---

设(f(n,k)=sum_{i=0}^kinom{n}{i})

[egin{aligned} &f(n,k)\ =&sum_{i=0}^kinom{n/p}{i/p}inom{n\%p}{i\%p}\ =&sum_{j=0}^{k/p-1}inom{n/p}{j}sum_{i=0}^{p-1}inom{n\%p}{i}+inom{n/p}{k/p}sum_{i=0}^{k\%p}inom{n\%p}{i}\ =&f(n/p,k/p-1)f(n\%p,p-1)+inom{n/p}{k/p}f(n\%p,k\%p) end{aligned} ]

然后就是注意边界边界边界...wa了好久...

---

Code:

// luogu-judger-enable-o2
#include <cstdio>
#define ll long long
const int mod=2333;
int C[mod+10][mod+10],f[mod+10][mod+10],T;
ll n,k;
void init()
{
    f[0][0]=C[0][0]=1;
    for(int i=1;i<mod;i++)
    {
        f[i][0]=C[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
            f[i][j]=(f[i][j-1]+C[i][j])%mod;
        }
    }
}
int getC(ll m,ll n)
{
    if(m<n) return 0;
    if(m<mod) return C[m][n];
    return getC(m/mod,n/mod)*getC(m%mod,n%mod)%mod;
}
int min(int x,int y){return x<y?x:y;}
int getF(ll n,ll k)
{
    if(k<0) return 0;
    if(!n) return 1;//f[0][k]...
    if(!k) return 1;//也许是n>=mod?的特判？
    if(n<mod) return f[n][min(n,k)];
    return (getF(n/mod,k/mod-1)*getF(n%mod,mod-1)%mod
           +getC(n/mod,k/mod)*getF(n%mod,k%mod)%mod)%mod;
}
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        printf("%d
",getF(n,k));
    }
    return 0;
}

---

2019.1.20