AcWing 1312. 序列统计（组合计数）

题意：给定三个正整数 N,L,R，统计长度在 1 到 N 之间，元素大小都在 L 到 R 之间的单调不降序列的数量。 思路：假设是求元素大小在L到R之间单调递增的序列的数量，那方案数可以简单的表达为$C（k，R-L+1）$，可以想到前者实际是后者的变形，前者可以表达为$C（k，R-L+k）$。 然后对求和公式进行化简，考研一些常用的技巧，最后用到lucas定理求解。

int t; int mo = 1e6 + 3; ll C(int a, int b) { if (a < b)return 0; ll be = 1, ed = 1; f(i, 1, b) { be = be * i%mo; ed = ed * (a - i + 1) % mo; } return ed * inv(be, mo) % mo; } ll lucas(int a, int b) { if (a < mo&&b < mo)return C(a, b); return lucas(a / mo, b / mo)*C(a%mo, b%mo) % mo; } int main() { //freopen("in.txt", "r", stdin); cin >> t; int cas=0; while (t--) { int n, l, r; cin >> n >> l >> r; cout << (lucas(r - l + n +1, r - l + 1)-1+mo)%mo << endl; } return 0; }