Description

有nn艘飞船，每艘飞船有一个武力值wiw_i。你需要把它们分成两队，每队飞船数目任意。

如果两艘飞船ii和jj 的武力值相加不小于mm且不在同一队，那么这两艘飞船就能配合默契

问最多能有多少飞船配合默契（不一定是一一配对，可以多对多），同时还需算出有多少种分队方案可以达到此效果

第二问对109+710^9+7取模

Hint

n≤2000,m≤2∗106,wi≤106n\leq 2000, m\leq 2 * 10^6, w_i \leq 10^6

Solution

将ww排序后，考虑在[l,t][l,t]这段区间中

若 w1+wn<mw_1+w_n < m，那么w1w_1与区间中所有飞船配合都不默契，递归处理[l+1,r][l+1,r]

若 w1+wn>=mw_1+w_n >= m，那么wnw_n与区间中所有飞船配合都默契，递归处理[l,r−1][l,r-1]

将这些数字依次取出，就能得到一个新的顺序

在这个新的顺序中，我们不关心每一个具体的ww的值，只关心它是否能与其他飞船配合默契

设op[i]op[i]表示第ii艘飞船是否能与其后面的所有飞船配合默契（要么全部都能，要么全部都不能）

再把数组翻转一下便于dp处理（翻转之后op[i]op[i]表示第ii艘飞船是否能与其前面的所有飞船配合默契）

设f[i][j]f[i][j]表示，考虑完了前ii艘飞船，其中有jj艘属于第一队的最多默契数

f[i][j]=max(f[i−1][j−1]+op[i]∗(i−j),f[i−1][j]+op[i]∗j)f[i][j]=max(f[i-1][j-1]+op[i] * (i-j), f[i-1][j]+op[i] * j)

（max前半部分表示选进第一队，后半部分表示选进第二队）

方案数类似转移，直接累加即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T> T read()
{
	T fl = 1, sum = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}

const int Maxn = 2000 + 10, Mod = 1e9 + 7;

int N, M, A[Maxn], op[Maxn], f[Maxn][Maxn], g[Maxn][Maxn], ans1, ans2, cnt;

inline void Solve (int l, int r)
{
	if (cnt == N) return ;
	if (A[l] + A[r] < M) { op[++cnt] = 0; Solve(l + 1, r); }
	else { op[++cnt] = 1; Solve(l, r - 1); }
}

int main()
{
	freopen("divide.in", "r", stdin);
	freopen("divide.out", "w", stdout);
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
	sort(A + 1, A + N + 1);
	Solve(1, N);
	reverse(op + 1, op + N + 1);
//	for (int i = 1; i <= N; ++i) cout<<op[i]<<" ";
//	puts("");
	memset(f, -0x3f3f3f3f, sizeof f);
	f[0][0] = 0;
	g[0][0] = 1;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j <= i; ++j)
		{
			if (!j)
			{
				f[i][j] = f[i - 1][j] + op[i] * j;
				g[i][j] = g[i - 1][j];
				continue;
			}
			int tmp1 = f[i - 1][j - 1] + op[i] * (i - j), tmp2 = f[i - 1][j] + op[i] * j;
			if (tmp1 == tmp2) f[i][j] = tmp1, g[i][j] = (g[i - 1][j - 1] + g[i - 1][j]) % Mod;
			else if (tmp1 < tmp2) f[i][j] = tmp2, g[i][j] = g[i - 1][j];
			else f[i][j] = tmp1, g[i][j] = g[i - 1][j - 1];
		}
	}
	for (int i = 0; i <= N; ++i)
	{
//		cout<<f[N][i]<<" ";
		if (f[N][i] > ans1 && g[N][i]) ans1 = f[N][i], ans2 = g[N][i];
		else if (f[N][i] == ans1) (ans2 += g[N][i]) %= Mod;
	}
//	puts("");
	cout<<ans1<<" "<<ans2<<endl;
	return 0;
}