LOJ10235 序列统计

题目链接

题目要求单调不降很不好做。
我们把每个数都加上它的下标，就变成了单调上升序列，值域是\([l+1,r+n]\)

在\([l+1,r+n]\)里面选\(n\)个数和单调上升序列的方案数是一一对应的。
答案是\(\sum_{i=1}^n\binom{r-l+i}{i}=\binom{r-l+n+1}{n}-1\)

因为模数是小质数，用\(lucas\)定理做就可以了。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int p = 1e6 + 3;
int n, l, r, a[p + 5];

int fpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * 1ll * a % p) if (b & 1) res = res * 1ll * a % p;
	return res;
}
int C(int n, int m) {
	if (m > n) return 0;
	return a[n] * 1ll * fpow(a[n - m], p - 2) % p * 1ll * fpow(a[m], p - 2) % p;
}
int solve(int n, int m) {
	if (m == 0) return 1;
    return solve(n / p, m / p) * 1ll * C(n % p, m % p) % p;
}

int main() {
    int -;
	a[0] = 1;
	for (int i = 1; i <= p; i++) a[i] = a[i - 1] * 1ll * i % p;
	for (scanf("%d", &-); -; ---) {
        scanf("%d %d %d", &n, &l, &r);
		printf("%lld\n", (solve(r - l + 1 + n, n) * 1ll - 1ll + p) % p);
	}
	return 0;
}

```