[BZOJ 4403] 序列统计

题目大意

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

1T1001 \leqslant T \leqslant 100

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

题目链接

BZOJ 4403

题解

对于一个固定的序列长度 ii,所求答案即从 [1, rl+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;
}