2019-10-23 11:00:35

• $j<i$
• $S_i-S_j\geq A$
• 对于 $[j+1,i-1]$ 中任意两个数 $x<y$ ，满足 $S_y-S_x\geq B$

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

ll X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}

const int N=100000+10;
const int mod=1e9+7;

int n; ll A,B,a[N];
int dp[N],sum[N];

int main() {
for (re int i=1;i+2<=n;++i)
if (a[i+2]-a[i]<B) { puts("0"); return 0; }
dp[0]=sum[0]=1;
for (re int i=1,p=0,q=0;i<=n;++i) {
while (q<i&&a[i]-a[q+1]>=A) ++q;
if (p<=q) dp[i]=(dp[i]+(sum[q]-(p?sum[p-1]:0)+mod)%mod)%mod;
sum[i]=(sum[i-1]+dp[i])%mod;
if (i>1&&a[i]-a[i-1]<B) p=i-1;
}
int ans=0;
for (re int i=n;~i;--i) {
ans=(ans+dp[i])%mod;
if (i<n&&a[i+1]-a[i]<B) break;
}
printf("%d\n",ans);
return 0;
}
• star
首页