序列统计

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1703 字
统计长度在1到N之间、元素都在[L,R]内的
一本通
练习
正文

/*
原题：T1657「一本通 6.6 练习 6」序列统计
题意：统计长度在 1 到 N 之间、元素都在 [L,R] 内的单调不降序列的个数，模 10^6+3。
思路：设元素种类数 m=R-L+1。长度为 i 的单调不降序列数等价于从 m 种元素中
可重复地取 i 个，即 C(m+i-1, i)。由曲棍球杆恒等式，Σ_{i=1}^{N} C(m+i-1,i)
= C(m+N, N) - 1，所以只需一次组合数。用 Lucas 定理在模 10^6+3 下求值。
复杂度：时间 O(log_p n)，空间 O(1)
易错点：1) 序列长度是 1 到 N 而不是固定 N，最后要减去 i=0 时的空序列 1；
2) 等效{matrix}公式是 C(m+i-1,i) 而非 C(m,i)（可重复选取）；
3) 减 1 后可能为负，要先加模数。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=1000003;
long long qpow(long long a,long long n){
    long long r=1;
    a%=MOD;
    while(n>0){
        if(n&1){
            r=r*a%MOD;
        }
        a=a*a%MOD;
        n>>=1;
    }
    return r;
}
vector<long long> fact,ifact;
void build(long long upto){
    fact.assign(upto+1,1);
    for(long long i=1;i<=upto;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    ifact.assign(upto+1,1);
    ifact[upto]=qpow(fact[upto],MOD-2);
    for(long long i=upto-1;i>=0;i--){
        ifact[i]=ifact[i+1]*(i+1)%MOD;
    }
}
long long combSmall(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    return fact[n]*ifact[m]%MOD*ifact[n-m]%MOD;
}
long long lucas(long long n,long long m){
    if(m<0 || m>n){
        return 0;
    }
    long long res=1;
    while(n>0 || m>0){
        res=res*combSmall(n%MOD,m%MOD)%MOD;
        n/=MOD;
        m/=MOD;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        long long N,L,R;
        cin>>N>>L>>R;
        long long len=R-L+1;
        long long top=N+len;
        build(min(top,MOD-1));
        long long ans=(lucas(top,N)-1)%MOD;
        if(ans<0){
            ans+=MOD;
        }
        cout<<ans<<"\n";
    }
    return 0;
}
序列统计

正文

一本通·提高篇的其它内容
