一、题目
二、解法
首先有一个 \(\tt naive\) 的简单 \(dp\)，设 \(f[i]\) 表示最后一个 \(A\) 集合选取的数是 \(a_i\)，合法的集合划分方案数，转移可以枚举上一个选取的 \(j\)，那么限制是：
- \(a_i-a_j\geq A\)
- \(\forall k\in[j+1,i-1),a_{k+1}-a_k\geq B\)
但是发现限制显然是不够的，因为可能有 BAB....A 这种情况，那么被转移点 \(j\) 分开的两个 \(B\) 集合的限制就没有考虑到，但是限于 \(dp\) 我们难以处理这个限制。
这个点睛之笔我已经快要想到了，其实就是弱化这个限制直到我们不需要考虑它也可以合法，我们可以通过交换保证 \(A>B\)，然后发现有解的必要条件是 \(\forall i,a_{i+1}-a_{i-1}\geq B\)，我们可以先判断有无解然后这个限制就自动合法了。
这两个限制可以分别维护两个指针，那么合法 \(j\) 的范围就是一段区间，直接用前缀和优化即可。
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 100005;
const int MOD = 1e9+7;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,A,B,ans,a[M],f[M],s[M];
signed main()
{
n=read();A=read();B=read();
if(A<B) swap(A,B);
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=3;i<=n;i++) if(a[i]-a[i-2]<B)
{
puts("0");
return 0;
}
f[0]=s[0]=1;
for(int i=1,p=0,q=0;i<=n;i++)
{
while(q<i && a[i]-a[q+1]>=A) q++;
if(p<=q) f[i]=(s[q]-(p?s[p-1]:0))%MOD;
s[i]=(s[i-1]+f[i])%MOD;
if(i>1 && a[i]-a[i-1]<B) p=i-1;
}
for(int i=n;i>=0;i--)
{
ans=(ans+f[i])%MOD;
if(i<n && a[i+1]-a[i]<B) break;
}
printf("%lld\n",(ans+MOD)%MOD);
}