给出一个长度为n~(2\leq n \leq 5000)的数组a_1,a_2,a_3,...,a_n~(1\leq a_i \leq 10^9)，求有多少种将a重新排列后的b满足对\forall~ 2 \leq i \leq n都有b_i \geq 2max\{b_1,b_2,...,b_{i-1} \}或2b_i \leq max\{b_1,b_2,...,b_{i-1} \}。
先将数组a升序排序。用f[i][j]表示最大值为a[i]长度为j的序列总数。考虑如下两种转移：
- 在序列末尾加入一个大于两倍最大值的数，
f[k][j+1] \leftarrow f[i][j]，a_k \geq 2a_i，实现时使用前缀和优化 - 从满足
2a_k \leq a_i且未在序列中的数a_k中选择一个加入序列末尾，f[i][j+1] \leftarrow f[i][j] * (k - j + 1)，其中k表示最大的k满足2a_k \leq a_i
时间复杂度O(n^2)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5010;
const int mod = 998244353;
int a[maxn];
int sum[maxn][maxn], f[maxn][maxn];
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
int t = 0; sum[0][0] = 1;
for (int i = 1; i <= n; i++) {
while (2 * a[t + 1] <= a[i]) t++;
for (int j = 1; j <= i; j++) {
f[i][j] = sum[t][j - 1];
if (j - 1 <= t) {
(f[i][j] += 1ll * f[i][j - 1] * (t - j + 2) % mod ) %= mod;
}
}
for (int j = 0; j <= i; j++)
sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
}
cout << f[n][n] << endl;
}