Description
给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。
Input
输入第一行包含一个整数T，表示数据组数。
第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。
1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。
Output
输出包含T行，每行有一个数字，表示你所求出的答案对10^6+3取模的结果。
Sample Input
2
1 4 5
2 4 5
1 4 5
2 4 5
Sample Output
2
5
//【样例说明】满足条件的2个序列为[4]和[5]。
5
//【样例说明】满足条件的2个序列为[4]和[5]。
HINT
Source
By yts1999
Solution
我们可以将原问题为有R-L+1个人，有n个物品分给这些人并且可以有人没被分到的方案数。
为什么呢？
因为R-L+1个数每个数分到的物品即为这个数列中选择的这个数的个数。那么将这个数列排序即有且只有一种情况使得这个数列成为单调不降序列。
所以两种不同的序列的不同即在有些数选的个数不同。
由于序列长度不一定为n,所以相当于多一个人来分这n个物品。
所以最终答案为C(R-L+1,n+R-L+1)-1（最后-1是因为序列不能为空）。
|
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 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long #define mo 1000003 using namespace std; int f[mo+5],inv[mo+5]; void pre() { f[0]=inv[1]=1; for (int i=1;i<mo;i++) f[i]=(ll)f[i-1]*i%mo; for (int i=2;i<mo;i++) inv[i]=(ll)(mo-mo/i)*inv[mo%i]%mo; } int C(int x,int y) { if (x>y) return 0; return (ll)f[y]*inv[f[x]]%mo*inv[f[y-x]]%mo; } int lucas(int x,int y) { if (x>y) return 0; if (y<mo) return C(x,y); return (ll)lucas(x/mo,y/mo)*C(x%mo,y%mo)%mo; } int main() { int T; scanf("%d",&T); pre(); while (T--) { int n,l,r; scanf("%d%d%d",&n,&l,&r); printf("%d\n",(lucas(r-l+1,r-l+n+1)-1+mo)%mo); } return 0; } |
