正题

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4403

---

题目大意

求有多少个长度为$n$的单调不升序列，且对于每个元素都$\in [L,R]$

---

解题思路

我们让$m=R-L+1$，因为序列的要求起始起始不会影响结果
然后我们开始考虑，我们在长度为$n$的序列全中1序列中我们可以每次选择一个位置让后面的数都加1，然后选择的个数不能超过$m-1$个。

我们枚举进行了多少次操作，对于操作的先后顺序不会影响该结果，然后这时我们可以将模型转换为$n$个格子，$i$个球，然后求方案数
$$\sum _{i=1}^{m-1}{C}_{n+i-1}^i\Rightarrow C_{n+m}^m-1$$

然后$Lucas$定理搞搞就好了时间复杂度$O(T\log n+p)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll p=1e6+3; ll T,n,m,a[p+1]; ll power(ll x,ll b,ll p) {ll ans=1;while(b){if(b&1) ans=ans*x%p;x=x*x%p;b>>=1;}return ans; } ll C(ll n,ll m,ll p) {if(m>n) return 0ll;return a[n]*power(a[m],p-2,p)%p*power(a[n-m],p-2,p)%p; } ll lucas(ll n,ll m,ll p) {if(!m) return 1ll;return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p; } int main() {scanf("%lld",&T);a[0]=1;for(ll i=1;i<=p;i++)a[i]=a[i-1]*i%p;while(T--){int r,l;scanf("%lld%lld%lld",&n,&l,&r);m=r-l+1;printf("%lld\n",(lucas(n+m,m,p)-1+p)%p);}return 0; }

总结

以上是生活随笔为你收集整理的bzoj4403-序列统计【Lucas,组合数学】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。