题意
给定序列 \(S\)。
求满足以下性质的 \(S\) 的排列的数量：
\(\max_{j = 1} ^ {i - 1} s_j \ge 2 \times s_i\) 或 \(\max_{j = 1} ^ {i - 1} 2 \times s_j \le s_i\)。
Sol
排个序先。
设 \(f_i\) 表示我们从小到大往 \(s\) 里面填数，现在填的最大值为 \(s_i\) 的方案数。
不难想到如果我们当前填了 \(s_i\)，考虑最大的 \(lst_i = j\) 满足 \(2 \times s_j \le s_i\)，所有小于等于 \(lst_i\) 的数都已经被填了。
所以转移就很简单了：
\(f_i = \sum_{j = 0} ^ {lst_i} f_j \times A_{n - 2 - lst_j} ^ {lst_i - lst_j - 1}\)。
时间复杂度：\(O(n ^ 2)\)。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 5005, mod = 998244353;
namespace Mth {
int pow_(int x, int k, int p) {
int ans = 1;
while (k) {
if (k & 1) ans = ans * x % p;
x = x * x % p;
k >>= 1;
}
return ans;
}
array <int, N> fac, inv;
void Mod(int &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
inv[n] = pow_(fac[n], mod - 2, mod);
for (int i = n; i; i--)
inv[i - 1] = inv[i] * i % mod;
}
int A(int n, int m) {
if (m > n) return 0;
return fac[n] * inv[n - m] % mod;
}
}
array <int, N> s, lst;
array <int, N> f;
signed main() {
int n = read();
for (int i = 1; i <= n; i++)
s[i] = read();
sort(s.begin() + 1, s.begin() + 1 + n);
for (int i = 1; i <= n; i++) {
lst[i] = lst[i - 1];
while (s[lst[i] + 1] * 2 <= s[i]) lst[i]++;
}
f[0] = 1, lst[0] = -1;
Mth::init(n);
/* write(Mth::fac[3] * Mth::inv[2] % mod), puts(""); */
for (int i = 1; i <= n; i++)
for (int j = 0; j <= lst[i]; j++)
f[i] += f[j] * Mth::A(n - lst[j] - 2, lst[i] - lst[j] - 1) % mod, Mth::Mod(f[i]);
if (lst[n] != n - 1) puts("0");
else write(f[n]), puts("");
return 0;
}