题目地址：BZOJ：Problem 4403. — 序列统计

题目描述

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。

输入输出格式

输入格式：
输入第一行包含一个整数T，表示数据组数。
第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。
1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

输出格式：
输出包含T行，每行有一个数字，表示你所求出的答案对10^6+3取模的结果。

输入输出样例

输入样例#1：

2
1 4 5
2 4 5

输出样例#1：

2
5

题解

本题需要的数学姿势：卢卡斯定理原理及应用 | KSkun’s Blog
首先，本题只需选出数而不在意它们的顺序，我们考虑转化成n个小球放入m=r-l+1个盒子里这个问题，使用插板法，得到m个数组成长度为n的不下降序列的方案数为\mathrm{C}_{n+m-1}^{m-1}，也就是说，我们想求的答案是\sum_{i=1}^n \mathrm{C}_{i+m-1}^{m-1}。
我们知道有公式\mathrm{C}_i^j = \mathrm{C}_{i-1}^j + \mathrm{C}_{i-1}^{j-1}，我们来利用这个公式合并每一项。
\begin{aligned} & \mathrm{C}_{1+m-1}^{m-1} + \mathrm{C}_{2+m-1}^{m-1} + \cdots + \mathrm{C}_{n+m-1}^{m-1} \\ =& \mathrm{C}_{1+m-1}^m + \mathrm{C}_{1+m-1}^{m-1} + \mathrm{C}_{2+m-1}^{m-1} + \cdots + \mathrm{C}_{n+m-1}^{m-1} - 1 \\ =& \mathrm{C}_{1+m}^m + \mathrm{C}_{1+m}^{m-1} + \cdots + \mathrm{C}_{n+m-1}^{m-1} - 1 \\ =& \mathrm{C}_{2+m}^m + \mathrm{C}_{2+m}^{m-1} + \cdots + \mathrm{C}_{n+m-1}^{m-1} - 1 \\ =& \cdots \\ =& \mathrm{C}_{n+m}^m - 1 \end{aligned}
这个可以利用Lucas定理解决。

代码

// Code by KSkun, 2018/4
#include <cstdio>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005, MO = 1000003;

LL T, n, l, r, mul[MAXN], inv[MAXN];

inline LL C(LL n, LL m) {
    if(m > n) return 0;
    return mul[n] * inv[n - m] % MO * inv[m] % MO;
}

inline LL lucas(LL n, LL m) {
    if(!m) return 1;
    return lucas(n % MO, m % MO) * lucas(n / MO, m / MO) % MO;
}

inline void cal() {
    mul[0] = mul[1] = inv[0] = inv[1] = 1;
    for(int i = 2; i < MO; i++) {
        inv[i] = (-(MO / i) * inv[MO % i] % MO + MO) % MO;
    }
    for(int i = 2; i < MO; i++) {
        mul[i] = mul[i - 1] * i % MO;
        inv[i] = inv[i - 1] * inv[i] % MO;
    }
}

int main() {
    T = readint();
    cal();
    while(T--) {
        n = readint(); l = readint(); r = readint();
        LL m = r - l + 1;
        printf("%lld\n", (lucas(n + m, m) - 1 + MO) % MO);
    }
    return 0;
}