AcWing 1312. 序列统计
原题链接
中等
作者:
清风qwq
,
2022-07-08 13:31:51
,
所有人可见
,
阅读 133
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1000003;
int FastPower(int a, int k)
{
int res = 1;
while (k)
{
if (k & 1)res = (LL)res * a % mod;
a = (LL)a * a % mod;
k >>= 1;
}
return res;
}
int C(int a, int b)
{
if (a < b)return 0;
int res = 1, mul = 1;
for (int i = a - b + 1, j = 1; i <= a; i ++ , j ++ )
{
res = (LL)res * i % mod;
mul = (LL)mul * j % mod;
}
return (LL)res * FastPower(mul, mod - 2) % mod;
}
int lucas(int a, int b)
{
if (a < mod && b < mod)return C(a, b);
return (LL)C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
int n, l, r;
cin >> n >> l >> r;
cout << (lucas(r - l + n + 1, r - l + 1) - 1 + mod) % mod << endl;
}
return 0;
}