顺手搬一下吧··· in luogu
和其他题解不太一样的柿子。
把 0 元，50 元，100 元分别看成 \(-1\)，\(0\)，\(1\)，则问题转化成有多少种由 \(-1\)，\(0\)，\(1\)，构成的长为 \(n\) 的序列满足：
-
任意前缀和非负。
-
序列总和在 \([L,R]\) 之间。
由前一个条件可以想到卡特兰数。如果已经确定要用 \(n\) 个 \(1\)，\(m\) 个 \(-1\)，构成满足第一个条件的序列，则由卡特兰数得答案为 \(\binom{n+m}{n} - \binom{n+m}{n+1}\)。
于是想到先枚举 \(1\) 的个数，再枚举 \(-1\) 的个数。令 \(1\) 的个数为 \(i\)，\(-1\) 的个数为 \(j\)，容易得到符合条件的 \(j\) 的区间 \([l,r]\)。然后还要把这 \(i+j\) 个数放进序列里，方案为 \(\binom{n}{i+j}\)。
于是就有柿子：
\[\sum_{j=l}^{r}{\binom{n}{i+j}\cdot\left(\binom{i+j}{i}-\binom{i+j}{i+1} \right)} \]这个柿子括号里外都有 \(i+j\) 不太好化简的样子。不如先把它拆开，为：
\[\sum_{j=l}^{r}{\binom{n}{i+j}\cdot\binom{i+j}{i}}-\sum_{j=l}^{r}{\binom{n}{i+j}\cdot\binom{i+j}{i+1}} \]先看前面那部分，组合意义：先从 \(n\) 个里选 \(i+j\) 个，再从中选 \(i\) 个。不妨改变顺序，先从 \(n\) 个里选 \(i\) 个，再从剩下 \(n-i\) 个里选 \(j\) 个，于是就变成了：
\[\binom{n}{i}\cdot\sum_{j=l}^{r}{\binom{n-i}{j}} \]发现后面是组合数单行区间和的形式，等会可以解决。后半部分同理，下面有式子。
令 \(l_j,r_j\) 为一个 \(i\) 对应 \(j\) 的区间左右端点，总的柿子就变成了：
\[\sum_{i=L}^{n}{\left(\binom{n}{i}\cdot\sum_{j=l_i}^{r_i}{\binom{n-i}{j}}-\binom{n}{i+1}\cdot\sum_{j=l_i}^{r_i}{\binom{n-i-1}{j-1}}\right)} \]再来说那个组合数单行区间和。首先可以拆成前缀和相减，现在来讨论前缀和。设第 \(n\) 行前 \(m\) 列求和为 \(S(n,m)\)。
试着把每个 \(S\) 都写出来可以发现 \(S(n,m)=S(n-1,m-1)+S(n-1,m)\)，与组合数递推式相同。把 \(S(n,m)\) 的每个组合数都拆到上一行即可证明。
所以可以用一个指针记录某一位置的 \(S(n,m)\)，再来讨论指针的移动。
为了方便，\(S(n,m)\) 记为 \(y\)，指针再记录一个 \(S(n-1,m-1)\) 记为 \(x\)。
左右移动就直接计算单点组合数就可以做到。
下移：\(y\) 左移一位即可得到新的 \(x\)，再由新的 \(x\) 与旧的 \(y\) 加和，由上面的递推式得，即为新的 \(y\)。
上移：\(x\) 右移一位得到新的 \(y\)。如果现在要由 \(S(n,m)\) 得到 \(S(n-1,m)\)，可以知道：
\[S(n,m)=S(n-1,m-1)+S(n-1,m)=2\cdot S(n-1,m) -\binom{n-1}{m} \]所以 \(S(n-1,m)=\frac{S(n,m)+\binom{n-1}{m}}{2}\)。
要拿来减的左右前缀和分两个指针的话，可以发现每次要求的 \(S(n,m)\) 位置相近，直接暴力移指针即可。
然后这题又是个任意模数···把模数质因数分解成 \(\prod{p_i^{c_i}}\)，然后把每个数分成与模数互质的部分，用 \({p_i^{c`_i}}\) 来表示不互质的部分。互质的存在逆元，扩展欧几里得可以求，不互质的已经分解，乘除法容易定义，化成普通的形式可以加减。预处理出竭诚，组合数就可以求了。
···但是还有个问题，注意到 \(S(n,m)\) 的指针上移同时需要加法和除法，\(2\) 可能不存在逆元，要套用上面方法的话加法并不好定义，那怎么办呢？
···那就避免上移就好了。逆序枚举 \(i\)，总式子先算右边，就可以让指针单调不升了。上☆键☆已☆扣。
优雅的代码不会 #define int long long。码喵：
#include<bits/stdc++.h>
#define EL puts("Elaina")
#define reg register int
typedef long long ll;
using namespace std;
const int maxn=1e5+3,maxp=11;
int n,mod,L,R,cnt,p[maxp];
inline int qpow(int a,int b){
assert(b>=0);
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1)ans=1ll*ans*a%mod;
return ans;
}
inline void exgcd(int a,int b,ll &x,ll &y){
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x),y-=a/b*x;
}
inline int inv(int a){
ll x,y;exgcd(a,mod,x,y);
return (x+mod)%mod;
}
inline void init(){
int res=mod;
for(reg i=2;i*i<=mod;++i)
if(res%i==0){
p[++cnt]=i;
while(res%i==0)res/=i;
}
if(res^1)p[++cnt]=res;
}
struct number{
int c[maxp];
number(){}
number(ll x){
memset(c,0,sizeof(c));
for(reg i=1;i<=cnt;++i)
while(x%p[i]==0)c[i]++,x/=p[i];
c[0]=x;
}
inline int calc()const{
int ans=c[0];
for(reg i=1;i<=cnt;++i)if(c[i])
ans=1ll*ans*qpow(p[i],c[i])%mod;
return ans;
}
inline void operator *=(const number &a){
c[0]=1ll*c[0]*a.c[0]%mod;
for(reg i=1;i<=cnt;++i)c[i]+=a.c[i];
}
inline number operator *(const number &a)const{
number ans=*this;ans*=a;return ans;
}
inline void operator /=(const number &a){
c[0]=1ll*c[0]*inv(a.c[0])%mod;
for(reg i=1;i<=cnt;++i)c[i]-=a.c[i];
}
inline number operator /(const number &a)const{
number ans=*this;ans/=a;return ans;
}
}fac[maxn];
inline int C(int n,int m){
if(m>n)return 0;if(m==0||n==m)return 1;
return (fac[n]/fac[m]/fac[n-m]).calc();
}
struct CombinationPointer{
int n,m,x,y;
CombinationPointer(){n=m=1,x=1,y=2;}
inline void left(){
x=(1ll*x+mod-C(n-1,m-1))%mod;
y=(1ll*y+mod-C(n,m))%mod,--m;
}
inline void right(){
x=(1ll*x+C(n-1,m))%mod;
y=(1ll*y+C(n,m+1))%mod,++m;
}
inline void down(){
x=(1ll*y+mod-C(n,m))%mod;
y=(1ll*x+y)%mod,++n;
}
inline int query(int tx,int ty){
if(ty<0)return 0;
if(!tx)return 1;
if(!ty)return 1;
while(m>ty)left();
while(n<tx)down();
while(m<ty)right();
return y;
}
}p1,p2;
inline void MyDearMoments(){
scanf("%d%d%d%d",&n,&mod,&L,&R),init();
fac[0]=fac[1]=number(1);
for(reg i=2;i<=n;++i)fac[i]=fac[i-1]*number(i);
int ans=0;
for(reg i=n;i>=L;--i){
if(i==n){if(i>=L&&i<=R)ans=(ans+1)%mod;continue;}
int l=max(i-R,0),r=min(n-i,i-L);
if(l>r)continue;
if(!l)ans=(1ll*ans+C(n,i))%mod,++l;
if(l>r)continue;
ll res2=((1ll*p1.query(n-i-1,r-1)+mod-p2.query(n-i-1,l-2))%mod)%mod;
ll res1=((1ll*p1.query(n-i,r)+mod-p2.query(n-i,l-1))%mod)%mod;
res1=1ll*C(n,i)*res1%mod,res2=1ll*C(n,i+1)*res2%mod;
ans=((1ll*ans+res1)%mod+mod-res2)%mod;
}
printf("%d\n",ans);
}
int main(){return MyDearMoments(),0;}