[BZOJ 4403]序列统计：Lucas定理

本文主要是介绍[BZOJ 4403]序列统计：Lucas定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。
设M=R−L+1
长度为i，元素大小在1…M之间的单调不降序列的数量有C ( M−1 , i+M−1 ) 个 ，于是长度在1~N之间的数量有C ( M , N+M ) -1 个。
点击这里查看公式推导

/*
User:Small
Language:C++
Problem No.:BZOJ 4403
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const ll mod=1e6+3;
ll fac[mod],n,l,r;
ll exp_mod(ll a,ll b,ll p){ll res=1;while(b){if(b&1LL) res=res*a%p;a=a*a%p;b>>=1LL;}return res;
}
ll c(ll n,ll m,ll p){if(n<m) return 0;if(n==m) return 1;if(m>n-m) m=n-m;ll ans=1,cn=1,cm=1;for(int i=0;i<m;i++){cn=cn*(n-i)%p;cm=cm*(m-i)%p;}ans=cn*exp_mod(cm,p-2,p)%p;return ans;
}
ll lucas(ll n,ll m,ll p){ll ans=1;while(n&&m&&ans){(ans*=c(n%p,m%p,p))%=p;n/=p;m/=p;}return ans;
}
int main(){freopen("data.in","r",stdin);//int t;scanf("%d",&t);while(t--){scanf("%lld%lld%lld",&n,&l,&r);printf("%lld\n",(lucas(n+r-l+1,r-l+1,mod)+mod-1)%mod);}return 0;
}

这篇关于[BZOJ 4403]序列统计：Lucas定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---