C++14(g++5.4) 解法, 执行用时: 898ms, 内存消耗: 98532K, 提交时间: 2020-06-15 23:09:11

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 5e3 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, m, a, b, aa, bb;
int x[N];
pii tmpx[N];
int dp[N][N], sum[N];
void add(int &x, int y) { x += y; if(x>=mod) x -= mod; }
int Add(int x, int y) { x += y; return (x>=mod ? x-mod : x); }
int Sub(int x, int y) { x -= y; return (x<0 ? x+mod : x); }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> aa >> bb >> m;
	for(int i=1; i<=n; i++) 
	{
		cin >> x[i];
		tmpx[i] = {x[i], i};
	}
	sort(x+1, x+n+1);
	sort(tmpx+1, tmpx+n+1);
	for(int i=1; i<=n; i++)
	{
		if(tmpx[i].se==aa) a = i;
		if(tmpx[i].se==bb) b = i;
	}
	dp[0][a] = 1;
	for(int i=1; i<=m; i++)
	{
		for(int j=1; j<=n; j++) sum[j] = Add(sum[j-1], dp[i-1][j]);
		for(int j=1; j<=n; j++)
		{
			if(j==b) continue;
			if(j<b) 
			{
				add(dp[i][j], sum[j-1]);
				int p = upper_bound(x+j, x+b+1, (x[j]+x[b]+1)/2-1) - x - 1;
				add(dp[i][j], Sub(sum[p], sum[j]));
			}
			else
			{
				add(dp[i][j], Sub(sum[n], sum[j]));
				int p = upper_bound(x+b, x+j+1, (x[j]+x[b])/2+1) - x - 1;
				add(dp[i][j], Sub(sum[j-1], sum[p-1]));
			}
		}
	}
	int ans = 0;
	for(int i=1; i<=n; i++) add(ans, dp[m][i]);
	cout << ans;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 405ms, 内存消耗: 196600K, 提交时间: 2020-06-07 09:50:03

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N=5010;
const long long MOD=1e9+7;
long long dp[MAX_N][MAX_N];
long long sum[MAX_N];
int p[MAX_N];
int lx[MAX_N],ux[MAX_N];
int main(void){
	int n,a,b,m,i,j;
	scanf("%d%d%d%d",&n,&a,&b,&m);
	for(i=1;i<=n;i++)
	scanf("%d",&p[i]);
	a=p[a];b=p[b];
	sort(p+1,p+n+1);
	a=lower_bound(p+1,p+n+1,a)-p;
	b=lower_bound(p+1,p+n+1,b)-p;
	for(i=1;i<=n;i++){
		if(i==a)
		sum[i]=sum[i-1]+1;
		else
		sum[i]=sum[i-1];
	}
	dp[0][a]=1;
	for(j=1;j<=n;j++){
		lx[j]=lower_bound(p+1,p+n+1,(p[b]+p[j]+1)/2)-p-1;
		ux[j]=upper_bound(p+1,p+n+1,(p[b]+p[j])/2)-p;;
	}
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(p[j]<p[b]){
				//int x=lower_bound(p+1,p+n+1,(p[b]+p[j]+1)/2)-p-1;
				int x=lx[j];
				dp[i][j]=(sum[x]-dp[i-1][j]+MOD)%MOD;
			}
			else if(p[j]>p[b]){
				//int x=upper_bound(p+1,p+n+1,(p[b]+p[j])/2)-p;
				int x=ux[j];
				dp[i][j]=((sum[n]-sum[x-1]+MOD)%MOD-dp[i-1][j]+MOD)%MOD;
			}
		}
		for(j=1;j<=n;j++)
		sum[j]=(sum[j-1]+dp[i][j])%MOD;
	}
	long long ans=0;
	for(j=1;j<=n;j++){
		//cout<<j<<" "<<dp[m][j]<<"\n"; 
		ans=(ans+dp[m][j])%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}