BZOJ4403 序列统计

题意

求长度在 $1\sim N$ 之间，由 $[L,R]$ 之间的数构成的单调不降序列的个数。

$N,L,R\le 10^{9}$ 。多组数据，组数 $t\le 100$ 。

题解

令 $M=R-L+1$ ，即可以使用的数的个数。

先考虑固定长度为 $n$ 的情况。

因为是单调不降，所以数字可以重复使用，而只要选出一部分数就能构成一个且仅有一个满足要求的序列。答案就等价于从 $M+n$ 个数中选出 $n$ 个的方案数，即

$$C_{M+n-1}^n$$

那么所有长度的情况即为

$$\begin{aligned} & \sum\limits_{i = 1} ^ N C(i + M - 1, i) \\ = & \sum\limits_{i = 1} ^ N C(i + M - 1, M - 1) \\ = & \sum\limits_{i = 1} ^ N C(i + M - 1, M - 1) + C(m, m) - 1 \\ = & \sum\limits_{i = 2} ^ N C(i + M - 1, M - 1) + C(m, m - 1) + C(m, m) - 1 \\ = & \sum\limits_{i = 2} ^ N C(i + M - 1, M - 1) + C(m + 1, m) - 1 \\ = & \sum\limits_{i = 3} ^ N C(i + M - 1, M - 1) + C(m + 2, m) - 1 \\ = & C(m + n, m) - 1 \\ \end{aligned} $$

然后直接用 $\text{Lucas}$ 定理求解即可。

需要注意的是因为有 $-1$ ，所以可能出现负数。

#include<bits/stdc++.h>
#define ll long long
#define ha 1000003

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll t,n,l,r,fac[ha+2];

inline void get_fac()
{
    fac[0]=fac[1]=1;
    for (ll i=2;i<=ha;i++) fac[i]=fac[i-1]*i%ha;
}

inline ll qpow(ll x,ll y)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans;
}

inline ll inv(ll x) { return qpow(x,ha-2); }

inline ll C(ll n,ll m)
{
    if (m>n) return 0;
    return fac[n]*(inv(fac[m])*inv(fac[n-m])%ha)%ha;
}

inline ll lucas(ll n,ll m)
{
    if (!m) return 1;
    return lucas(n/ha,m/ha)*C(n%ha,m%ha)%ha;
}

signed main()
{
    get_fac();
    t=read();
    while (t--)
    {
        n=read(); l=read(); r=read();
        ll len=r-l+1;
        printf("%lld\n",(lucas(len+n,len)-1+ha)%ha);
    }
    return 0;
}