AcWing 1312. 序列统计
原题链接
中等
作者:
只想白嫖
,
2022-01-26 20:48:26
,
所有人可见
,
阅读 114
//author: A Fei
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e6+3;
int T;
int qmi(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % mod;
k >>= 1;
a = (LL)a * a % mod;
}
return res % mod;
}
int C(int a, int b)
{
if(a < b) return 0;//这一句直接能快三倍
int up = 1, down = 1;
for(int i = 1, j = a; i <= b; i ++, j --)
up = (LL)up * j % mod, down = (LL)down * i % mod;
return (LL)up * qmi(down % mod, mod - 2) % mod;
}
int Lucas(int a, int b)
{
if(a < mod && b < mod) return C(a, b) % mod;
return (LL)C(a % mod, b % mod) * Lucas(a / mod, b / mod) % mod;
}
int main()
{
scanf("%d", &T);
while(T --)
{
int n, l, r;
scanf("%d%d%d", &n, &l, &r);
int res = ((Lucas(r - l + n + 1, r - l + 1) - 1) % mod + mod) % mod;
printf("%d\n", res);
}
return 0;
}