形式化题目

给定整数 $N, L, R$（$1 \leqslant N, L, R \leqslant 10^9$，$L \leqslant R$），统计满足以下条件的整数序列 $a_1 \le a_2 \le \cdots \le a_k$ 的个数，对 $10^6+3$ 取模：

1. 长度 $k$ 满足 $1 \leqslant k \leqslant N$；
2. 每个元素都在 $[L, R]$ 内；
3. 序列单调不降。

$T \leqslant 100$ 组询问，每组独立作答。

正解

思路

第一步：固定长度，隔板法计数。 设值域大小 $m = R - L + 1$。长度为 $k$ 的单调不降序列，把每个元素减去 $L$ 后就是 $0 \le b_1 \le \cdots \le b_k \le m-1$，等价于"把 $k$ 个相同的球放进 $m$ 个有编号的盒子"（第 $i$ 个盒子里放值 $i$ 出现的次数）。隔板法给出方案数——多重组合数：

于是答案形如 $\sum_{k=1}^{N} \binom{m+k-1}{k}$，有 $N$ 项，$N$ 可达 $10^9$，逐项求和不可行。

第二步：hockey-stick 恒等式折叠求和。 把每项改写成 $\binom{m+k-1}{k} = \binom{m+k-1}{m-1}$，让下标固定、上标随 $k$ 连续变化，正好是恒等式 $\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}$ 的形状（取 $r = m-1$）：

含 $N+1$ 项的求和被折叠成一个组合数。它的直观含义：在 $m+N$ 个位置里选 $N$ 个位置放"球"，剩下 $m$ 段空隙的长度分布恰好编码一个长度不超过 $N$ 的单调不降序列。

用样例 2（$N=2, L=4, R=5$，即 $m = 2$）验证这个折叠。下表逐行列出"长度为 $k$ 的方案数"并累加：

观察重点：上表逐项累加到 $k=N$ 的前缀和 $6$，恰好等于折叠式 $\binom{m+N}{N} = \binom{4}{2} = 6$——这正是恒等式在断言"斜线求和 = 右下一格"。其中 $k=0$ 的空序列是恒等式顺带计入的，不属于题目要求，减 $1$ 后得 $5$，正是样例 2 的答案；同理样例 1（$N=1$）为 $\binom{3}{1} - 1 = 2$。

第三步：Lucas 定理求大组合数取模。 剩下的问题是求 $\binom{m+N}{N} \bmod p$，其中 $p = 10^6+3$ 是质数，而 $m+N \leqslant 2 \times 10^9 + 1 > p$，不能直接用阶乘逆元公式。用 Lucas 定理把 $m+N$ 和 $N$ 写成 $p$ 进制，逐位相乘：

每一位的参数都小于 $p$，预处理 $0..p-1$ 的阶乘表，用费马小定理求逆元即可 $O(1)$ 完成一位；$p$ 进制只有约 3 位，单次询问开销极小。

最终公式：

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:21
# update_at: 2026-10-01 00:21

import sys

P = 10**6 + 3  # 模数，质数：小于它的阶乘模它非零，Lucas 分解可用

# 阶乘表：P 以内的 i! mod P，Lucas 每一位的组合数都靠它
fact = [1] * P
for i in range(1, P):
    fact[i] = fact[i - 1] * i % P


def comb(n: int, k: int) -> int:
    """求 C(n, k) mod P：n 可达 2e9 超过 P，按 Lucas 定理按 P 进制逐位组合。"""
    res = 1
    while n or k:
        a, b = n % P, k % P   # 当前 P 进制位
        if b > a:             # 某一位下标超过上标，整项为 0
            return 0
        res = (res * fact[a] * pow(fact[b], P - 2, P) * pow(fact[a - b], P - 2, P)) % P
        n, k = n // P, k // P
    return res


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    out: list[str] = []

    for _ in range(T):
        n, l, r = next(data), next(data), next(data)
        m = r - l + 1              # 元素取值个数
        # 按长度枚举求和得 hockey-stick 恒等式：Σ_{i=1..n} C(m+i-1, i) = C(m+n, n)
        # 非空序列至少含一个元素，从"长度 0 的空序列"对应的那 1 项里扣掉
        out.append(str((comb(m + n, n) - 1) % P))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:54
 * update_at: 2026-10-06 00:54
 */
#include <cstdio>

typedef long long ll;

const ll P = 1000003; // 模数，质数，Lucas 分解的进制

ll fact[1000003]; // fact[i] = i! mod P，供 Lucas 每一位查表

// 快速幂：求 base^exp mod P，用于费马小定理求逆元
ll power(ll base, ll exp) {
    ll res = 1;
    base %= P;
    while (exp > 0) {
        if (exp & 1) {
            res = res * base % P;
        }
        base = base * base % P;
        exp >>= 1;
    }
    return res;
}

// 组合数 C(n, k) mod P：n 可达 2e9 超过 P，按 Lucas 定理逐位相乘
ll comb(ll n, ll k) {
    ll res = 1;
    while (n > 0 || k > 0) {
        ll a = n % P; // 当前 P 进制位
        ll b = k % P;
        if (b > a) {
            return 0; // 某一位下标超过上标，整项为 0
        }
        res = res * fact[a] % P;
        res = res * power(fact[b], P - 2) % P;
        res = res * power(fact[a - b], P - 2) % P;
        n /= P;
        k /= P;
    }
    return res;
}

int main() {
    fact[0] = 1;
    for (ll i = 1; i < P; i++) {
        fact[i] = fact[i - 1] * i % P;
    }

    ll t;
    scanf("%lld", &t);
    while (t--) {
        ll n, l, r;
        scanf("%lld%lld%lld", &n, &l, &r);
        ll m = r - l + 1; // 元素取值个数
        // 逐长度求和由 hockey-stick 恒等式折叠为 C(m+n, n)，
        // 该式包含了长度为 0 的空序列，题目要求长度至少为 1，故减 1
        ll ans = (comb(m + n, n) - 1 + P) % P;
        printf("%lld\n", ans);
    }
    return 0;
}

复杂度

• 时间：预处理阶乘表 $O(p)$（$p = 10^6+3$），每组询问 Lucas 拆位 $O(\log_p(m+N)) \approx 3$ 层、每层 $O(\log p)$ 次快速幂乘法，总计 $O\big(p + T\log^2 p\big)$。
• 空间：$O(p)$ 存阶乘表。

总结

• 计数模型：单调不降序列 = 可重组合，隔板法得 $\binom{m+k-1}{k}$。
• 关键一步：hockey-stick 恒等式把 $N+1$ 项求和折叠为 $\binom{m+N}{N}$，这是本题从"不可算"到"可算"的分水岭。
• 求值工具：模数 $10^6+3$ 为质数且小于组合数参数，Lucas 定理 + 阶乘表 + 费马逆元。
• 别忘了减 $1$：恒等式把空序列也计了进去。