题解：P16781 ⌈Xzy OI R1 T3⌋ 穿穿表

· · 题解

很牛的题啊。

我们注意到部分分给出了 k=0，0\le k \le 100，以及无限制。所以我们考虑分 k=0，k \le 100，k>100 三种情况讨论。

k=0

其实就是 2^b。

k\le 100

设答案的值为 f(b)。

观察一下当前的式子：

f(b)=\sum_{i=0}^{\lfloor\frac{b}{k}\rfloor} \binom{i}{b-ik}

我们知道 \binom{n}{m}=\binom{n-1}{m-1}+\binom{n}{m-1}。

所以上面的式子变为了（根据题意当 n=0 或 m=0 时，\binom{n}{m}=0）：

f(b)=\sum_{i=0}^{\lfloor\frac{b}{k}\rfloor} \left( \binom{i-1}{b-ik-1}+\binom{i}{b-ik-1}\right)

再拆开并整理一下：

f(b)=\sum_{i=0}^{\lfloor\frac{b}{k}\rfloor} \binom{i-1}{b-1-k-(i-1)k} + \sum_{i=0}^{\lfloor\frac{b}{k}\rfloor}\binom{i}{(b-1)-ik}

我们发现左边的式子恰好为 f(b-1-k)，而右边的式子恰好为 f(b-1)，所以有：

f(b)=f(b-1-k)+f(b-1);

由于 k\le 100，矩阵乘法即可。

这一部分复杂度为 O(k^3\log b)。

k>100

我们注意到这时抛开组合数的复杂度不谈，直接枚举的复杂度是 O(\lfloor \frac{b}{k} \rfloor)，并且 k>100 所以 \lfloor \frac{b}{k} \rfloor\le 2\times 10^7，这非常的小。

那么我们考虑怎么求巨大的组合数，我们注意到题目给出一下提示：

这十分有用！这告诉我们可以直接使用 Lucas 定理，而 Lucas 定理的复杂度为预处理 O(P)，单次求组合数 O(\log_{P}V)，其中 P 为模数，V 为值域。

这一部分复杂度为 O(P+\lfloor \frac{b}{k} \rfloor\log_{P}V)。

于是我们就通过了这一题，注意卡常。

代码

const int N=101,M=1145141;
int n;
struct mat{
    int c[N][N];
    int * operator[](int i){
        return c[i];
    }
    void clear(){
        memset(c,0,sizeof c);
    }
    void init(){
        clear();
        for(int i=0;i<N;i++)c[i][i]=1;
    }
    friend mat operator *(mat a,mat b){
        mat c;c.clear();
        for(int k=0;k<n;++k){
            for(int i=0;i<n;++i){
                for(int j=0;j<n;++j){
                    c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j]%M)%M;
                }
            }
        }return c;
    }
    friend mat operator ^(mat a,int b){
        mat ret;ret.init();
        while(b){
            if(b&1)ret=ret*a;
            a=a*a;
            b>>=1;
        }return ret;
    } 
}A,B;
int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1)ret=1ll*ret*a%M;
        a=1ll*a*a%M;
        b>>=1;
    }return ret;
}
int fac[2000000],inv[2000000];
inline int C(int n,int m){
    if(m>n)return 0;
    return 1ll*fac[n]*inv[m]%M*inv[n-m]%M;
}
inline int Lucas(int n,int m,int p){
    if(!m)return 1;
    return (1ll*Lucas(n/p,m/p,p)*C(n%p,m%p))%p; 
}
main(){
    int k,b;
    cin>>k>>b;
    if(b<=k){
        cout<<1;
        return 0;
    }
    if(k==0)cout<<qpow(2,b);
    else if(k<=100){
        n=k+1;
        for(int i=0;i<=k;i++)A[0][i]=1;
        for(int i=0;i<k;i++)B[i+1][i]=1;
        B[0][k]=1;
        B[k][k]=1;
        A=A*(B^b-k);
        cout<<A[0][k];
    }else{
        fac[0]=1;
        for(int i=1;i<1145141;++i)fac[i]=1ll*fac[i-1]*i%M;
        inv[1145140]=qpow(fac[1145140],M-2);
        for(int i=1145140;i;--i)inv[i-1]=1ll*inv[i]*i%M;
        int ans=0;
        for(int i=0;1ll*i*k<=1ll*b;++i)ans=(Lucas(b-i*k,i,M)+ans)%M;
        cout<<ans;
    }return 0;
}