题面在这里
首先元素大小在 [L,R] 等价于 [1,R−L+1]
那么长度为i,元素大小 [1,M] 的非降序列方案数为 CM−1i+M−1
所以答案就是:
∑i=1NCM−1i+M−1=(∑i=1NCM−1i+M−1)+CMM−1=(∑i=2NCM−1i+M−1)+CMM+1−1=(∑i=3NCM−1i+M−1)+CMM+2−1…=CMN+M−1
直接套用lucas定理即可
示例程序:
#include<cstdio>
typedef long long ll;
const int maxn=e6+,MOD=e6+;
int tst;
ll fac[maxn],inv[maxn];
void prepare(){
fac[]=;inv[]=inv[]=;
for (int i=;i<=MOD;i++) fac[i]=fac[i-]*i%MOD;
for (int i=;i<=MOD;i++) inv[i]=-(MOD/i)*inv[MOD%i]%MOD;
for (int i=;i<=MOD;i++) (inv[i]*=inv[i-])%=MOD;
}
ll C(int x,int y){
if (x>y) return ;
if (x<MOD&&y<MOD)
return fac[y]*inv[x]%MOD*inv[y-x]%MOD;
return C(x/MOD,y/MOD)*C(x%MOD,y%MOD)%MOD;
}
int main(){
prepare();
scanf("%d",&tst);
while (tst--){
int n,m,l,r;scanf("%d%d%d",&n,&l,&r);
m=r-l+;
printf("%lld\n",(C(m,n+m)-+MOD)%MOD);
}
return ;
}