给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。
给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。
输出包含T行，每行有一个数字，表示你所求出的答案对10^6+3取模的结果。
记得做过这样一道题：[Luogu 3902]Increasing
里面的思想就是将严格递增的序列第$i$个数减去$i$变成单调不下降的序列，来方便处理答案。
这里我们用相同的思想。由于原序列单调不下降，我们可以让第$i$个数加上一个$i$，使原序列单调递增。
这样取值范围就变成了$[L+1, R+n]$，一共$n+R-L$个数，这样对于长度为$n$的序列我们只要求$C^n _{n+R-L}$ = $C^{R-L} _{n+R-L}$。
然而到这里还没结束，题目要求的是长度为$[1, n]$。
简而言之就是求：
$$\sum _{i=1} ^n {C^{R-L} _{i+R-L}}$$
我们这里要想到这样一个公式：$C^m _n = C^{m-1} _{n-1}+C^m _{n-1}$，
我们再看上面这个式子，令$k = R-L$：
$ans=C_{1+k}^k+C_{2+k}^k+C_{3+k}^k+…+C_{n+k}^k$
$=C_{1+k}^{1+k}-1+C_{1+k}^k+C_{2+k}^k+C_{3+k}^k+…+C_{n+k}^k$
$=(C_{1+k}^{1+k}+C_{1+k}^k)+C_{2+k}^k+C_{3+k}^k+…+C_{n+k}^k-1$
$=(C_{2+k}^{1+k}+C_{2+k}^k)+C_{3+k}^k+…+C_{n+k}^k-1$
$=(C_{3+k}^{1+k}+C_{3+k}^k)+…+C_{n+k}^k-1$
$……$
$=C_{n+k+1}^{k+1}-1$。
求$C_{n+k+1}^{k+1}$用$Lucas$求就可以了。
1 //It is made by Awson on 2017.10.7 2 #include <map> 3 #include <set> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <cstdio> 10 #include <string> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 using namespace std; 19 const int N = 1e6+3; 20 21 int n, l, r; 22 int A[N+5], B[N+5]; 23 24 int C(int n, int m) { 25 if (m > n) return 0; 26 return (LL)A[n]*B[n-m]%N*B[m]%N; 27 } 28 int Lucas(int n, int m) { 29 if (!m) return 1; 30 return (LL)C(n%N, m%N)*Lucas(n/N, m/N)%N; 31 } 32 void work() { 33 scanf("%d%d%d", &n, &l, &r); 34 printf("%d\n", (Lucas(n+r-l+1, r-l+1)-1+N)%N); 35 } 36 int main() { 37 A[0] = B[0] = A[1] = B[1] = 1; 38 for (int i = 2; i <= N; i++) 39 B[i] = -(LL)(N/i)*B[N%i]%N; 40 for (int i = 2; i <= N; i++) 41 A[i] = (LL)A[i-1]*i%N, 42 B[i] = (LL)B[i-1]*B[i]%N; 43 int t; 44 scanf("%d", &t); 45 while (t--) 46 work(); 47 return 0; 48 }
原文：http://www.cnblogs.com/NaVi-Awson/p/7635993.html