BZOJ 4403序列统计
解析
序列满足单调不降序列，所以每个数可以选多次，我们可以把不同位置的同一个数看成多个，
这样 把区间为 \([L,R]\) 中的每一个数加上 \(i\) , 得到的区间大小为 \([L+1,R+n]\) , 也就是从 \(R-L+n\) 个数中选 \(n\) 个。
\[\begin{aligned}&{ \sum^n_{i=1}C^{i}_{R-L+i} } \\ =&{ \sum^n_{i=1}C^{R-L}_{R-L+i} } \end{aligned} \]暴力会 \(\mathbb{T}\) , 我们可以把上述式子化简，由杨辉三角可易得：
\[{\begin{aligned} C^{m}_n=C^m_{n-1}+C^{m-1}_{n-1}\end{aligned}} \]\(\therefore\) 加一项 \(\displaystyle {C^{R-L+1}_{R-L+1}}\) 再减去，式子可以压缩为：
\[{C^{R-L+n+1}_{R-L+1}} \]于是，终于可以快乐 \(\mathbb {Lucas}\) 啦！
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000003;
typedef long long LL;
LL n,l,r,t,len;
LL fac[mod+10],inv[mod+10];
LL C(LL x,LL y,LL p)
{
if(x<y) return 0;
return (fac[x]*inv[y]%p*inv[x-y]%p);
}
LL Lucas(LL x,LL y,LL p)
{
if(y==0) return 1;
return (C(x%p,y%p,p)*Lucas(x/p,y/p,p))%p;
}
void init()
{
fac[0]=1;
for(int i=1;i<mod;i++) fac[i]=fac[i-1]*i%mod;
inv[1]=1;
for(int i=2;i<mod;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
inv[0]=1;
for(int i=1;i<mod;i++) inv[i]=(inv[i-1]*inv[i])%mod;
return;
}
int main()
{
init();
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&l,&r);
len=r-l;
printf("%lld\n",(Lucas(len+n+1,len+1,mod)-1+mod)%mod);
}
return 0;
}
注意
-
\(C^x_y\) 当 $x > y $ 时， 等于 $ 0 $ 。
-
线性求逆元，求阶乘逆元。