首页技术正文

Count Sequences

攻城狮凌昊技术 2022年11月15日

0 收藏 616 点赞 4,222 浏览 1028 个字

$考虑问题的转换，即把用n个球，分为r-l+2个部分，其中第1部分表示该区域的球值为l，第二部分表示该区域的球值为l+1$

$……第r-l+2部分为不选该区域的球$

$该问题等价于在n+1个空中插r-l+1块板，其中一个空可以插多个也可以不插$

$方案数即为\binom{r-l+n+1}{n}$

$但长度为1-n,因此要减去所有板都在1的情况，即为\binom{r-l+n+1}{n}-1$

$当然，n,r,l很大，因此要用Lucas定理$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1100050;
const int MOD=1e6+3;
int cnt;
long long Pow(int a, int b, int p) {
    long long ans = 1;
    long long base = a;
    base %= p;    while (b) {
        if (b & 1) {
            ans *= base;
            ans %= p;
        }        base *= base;
        base %= p;
        b >>= 1;
    }    return ans;
}
long long inv(int a, int p) {
    return Pow(a, p - 2, p);
}
long long fac[MAXN], inv_fac[MAXN];
long long C(long long n, long long m) {
    if (m < 0) {
        return 0;
    }
    if (n < m) {
        return 0;
    }
    if (m == 0||n==m)
        return 1;    long long k = fac[n];
    long long ans = k * inv(fac[n - m],MOD);
    ans %= MOD;
    ans = ans * inv(fac[m],MOD);
    ans %= MOD;
    return ans;
}
long long Lucas(int n,int m)
{
if(!m)
{
return 1;
}
return C(n%MOD,m%MOD)*Lucas(n/MOD,m/MOD)%MOD;
}
int t;
long long n,l,r;signed main() {
fac[0] = 1;
for (int i = 1; i <= MOD-1; i++) {
    fac[i] = fac[i - 1] * i;
    fac[i] %= MOD;
}
scanf("%lld",&t);
while(t--)
{
scanf("%lld %lld %lld",&n,&l,&r);
printf("%lld\n",(Lucas(r-l+n+1,n)-1+MOD)%MOD);
}
}