[BZOJ 4403] 序列统计

发表于2017-04-07更新于2020-08-06

题目大意

给定三个正整数 nn、ll 和 rr，统计长度在 11 到 nn 之间，元素大小都在 ll 到 rr 之间的单调不降序列的数量。输出答案对 1,000,0031,000,003 取模的结果。多组询问。

1⩽T⩽1001 \leqslant T \leqslant 100

1⩽n, l, r⩽1,000,000,0001 \leqslant n, \ l, \ r \leqslant 1,000,000,000

题目链接

BZOJ 4403

题解

对于一个固定的序列长度 ii，所求答案即从 [1, r−l+1][1, \ r - l + 1] 中允许重复地选出ii个数的个数，那么，所求答案即：

\begin{align} \sum_{i = 1}^{n} \binom{m + i - 1}{i} &= \sum_{i = 1}^{n} \binom{m + i - 1}{m - 1}, \quad m = r - l + 1 \\ &= \sum_{i = 1}^{n} \binom{m + i - 1}{m - 1} + \binom{m}{m} - 1 \\ &= \sum_{i = 2}^{n} \binom{m + i - 1}{m - 1} + \binom{m}{m - 1} + \binom{m}{m} - 1 \\ &= \sum_{i = 2}^{n} \binom{m + i - 1}{m - 1} + \binom{m + 1}{m} - 1 \\ &= \sum_{i = 3}^{n} \binom{m + i - 1}{m - 1} + \binom{m + 2}{m} - 1 \\ &= \binom{m + n}{m} - 1\\ \end{align}

然后套 Lucas 定理直接算就行了（模数是质数）。

代码

这类题还是都写成 long long 比较省心啊。。。

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
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
const int MOD = 1e6 + 3;
long long fact[MOD];
long long calcFact() {
    fact[0] = 1;
    for (int i = 1; i < MOD; i++) fact[i] = fact[i - 1] * i % MOD;
}
long long pow(long long a, long long n) {
    long long res = 1;
    for (; n; n >>= 1, a = a * a %MOD) if (n & 1) res = res * a % MOD;
    return res;
}
long long inv(long long x) {
    return pow(x, MOD - 2);
}
long long combin(long long n, long long m) {
    if (n < m) return 0;
    if (n < MOD && m < MOD) return fact[n] * inv(fact[m]) % MOD * inv(fact[n - m]) % MOD;
    return combin(n / MOD, m / MOD) * combin(n % MOD, m % MOD) % MOD;
}
int main() {
    calcFact();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, l, r;
        scanf("%d %d %d", &n, &l, &r);
        int m = r - l + 1;
        printf("%lld\n", (combin(m + n, m) + MOD - 1) % MOD);
    }
    return 0;
}