题意
给定三个正整数N、L和R,统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。
自己xjbyy的解法
设m=r-l+1.
那么我们先枚举一个i表示这个单调不降序列有多少个不同的数, 那么
原式=
r
突然清醒
突然发现自己是zz:我们这个问题就直接相当于把”n个球放入m个盒子,盒子可以为空,球可以不选”,再减去n个球一个都不选的情况,那就直接是
#include<cstdio>
#include<algorithm>
const int P = 1e6 + 3;
typedef long long ll;
int T, n, m;
ll jx[P], jx_rev[P];
int C (int n, int m) {
if (m > n) return 0;
return jx[n] * jx_rev[m] % P * jx_rev[n - m] % P;
}
ll Lucas (int n, int m) {
if (m > n) return 0ll;
if (n < P) return C (n, m);
int k = C (n % P, m % P);
if (k) return Lucas (n / P, m / P) * k % P;
return 0ll;
}
ll quick_power (ll a, ll b) {
ll ret = 1;
for (; b; a = a * a % P, b >>= 1) if (b & 1) ret = ret * a % P;
return ret;
}
int main () {
scanf ("%d", &T);
int l, r;
jx[0] = 1; for (int i = 1; i < P; ++i) jx[i] = jx[i - 1] * i % P;
jx_rev[P - 1] = quick_power (jx[P - 1], P - 2);
for (int i = P - 2; ~i; --i) jx_rev[i] = jx_rev[i + 1] * (i + 1) % P;
while (T--) {
scanf ("%d%d%d", &n, &l, &r), m = r - l + 1;
printf ("%lld
", (Lucas (n + m, m) - 1 + P) % P);
}
return 0;
}