【题目】序列统计

LibreOJ10235. 序列统计

https://loj.ac/p/10235

2
1 4 5
2 4 5

2
5

题解

$$\sum_{n=1}^{N}C_{R-L+n}^n$$

\begin{align} &\sum_{n=1}^{N}C_{R-L+n}^n\\ =&\sum_{n=1}^{N}C_{R-L+n}^{R-L}\\ =&\sum_{n=1}^{N}C_{R-L+n}^{R-L}+C_{R-L+1}^{R-L+1}-1\\ =&\sum_{n=2}^{N}C_{R-L+n}^{R-L}+C_{R-L+1}^{R-L}+C_{R-L+1}^{R-L+1}-1\\ =&\sum_{n=2}^{N}C_{R-L+n}^{R-L}+C_{R-L+2}^{R-L+1}-1\\ =&\sum_{n=3}^{N}C_{R-L+n}^{R-L}+C_{R-L+2}^{R-L}+C_{R-L+2}^{R-L+1}-1\\ =&\sum_{n=3}^{N}C_{R-L+n}^{R-L}+C_{R-L+3}^{R-L+1}-1\\ &\vdots\\ =&C_{R-L+N+1}^{R-L+1}-1 \end{align}

代码

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e6 + 3;
long long fact[MOD + 10];

void init()
{
fact[0] = 1;
for (int i = 1; i <= MOD; i++)
fact[i] = fact[i - 1] * i % MOD;
}

long long fast_pow(long long a, long long b, long long p)
{
b %= p;
long long ans = 1;
while (b)
{
if (b % 2)
ans = a * ans % p;
a = a * a % p;
b /= 2;
}
return ans;
}

inline long long inv(long long x, long long p)
{
return fast_pow(x, p - 2, p);
}

long long comb(long long a, long long b, long long p)
{
if (b > a)
return 0;
if (a < p && b < p)
return fact[a] * inv(fact[b], p) % p * inv(fact[a - b], p) % p;
return comb(a % p, b % p, p) * comb(a / p, b / p, p) % p;
}

int main()
{
int n;
cin >> n;
init();
while (n--)
{
long long N, L, R;
cin >> N >> L >> R;
cout << ((comb(N + (R - L + 1), R - L + 1, MOD) - 1) % MOD + MOD) % MOD << endl;
}
return 0;
}