序列统计

LibreOJ-10235-序列统计

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int M = 1000003;

int power (int a, int b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}
int C (int n, int m, int p) {
    int a = 1, b = 1;
    for (int i = 1, j = n; i <= m; ++ i, -- j) {
        a = (LL)a * j % p;
        b = (LL)b * i % p;
    }
    return (LL)a * power(b, p - 2, p) % p;
}
int Lucas (LL n, LL m, int p) {
    if (n < p && m < p)
        return C(n, m, p);
    return (LL)C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

int main () {
    int T;
    cin >> T;
    while (T --) {
        int n, l, r;
        cin >> n >> l >> r;
        int res = Lucas(r - l + n + 1, r - l + 1, M) - 1;
        cout << (res % M + M) % M << endl;
    }
    return 0;
}