codeforces 1437 F

题目链接：https://codeforces.com/contest/1437/problem/F

一个很重要的性质：happy 的渔夫手中的鱼的重量一定是递增的，且每个 happy 渔夫的鱼都比前一个 happy 的渔夫重至少两倍
于是我们就可以枚举 happy 的渔夫，剩下的渔夫肯定都是 sad 的

首先将 (a) 排序，(dp[i]) 表示第 (i) 个渔夫是 happy 的方案数，
转移的时候，枚举前一个 happy 的渔夫 (j)
注意，前一个渔夫的 (a[j] <= frac{a[i]}{2}), 所以设 (px[i]) 为满足 (a[x] <= frac{a[i]}{2}) 的最大的位置 (x)
所以 (j) 只需要枚举到 (px[i]) 即可

同时，(px[i]) 以内的所有不是 happy 的渔夫肯定都是 sad 的，现在来考虑安排这些渔夫位置的方案数
当前已经安排好了 (i, j, px[j]) 这些渔夫，所以还剩余 (n - 2 - px[j]) 个空位，还有 (px[i] - px[j] - 1) 个渔夫需要安排(-1 是因为 (j) 在 (px[i]) 中)，剩下的渔夫要安排在渔夫 (i) 的后面才能保证他们是 sad，而后来的 happy 的渔夫肯定比当前 (i) 渔夫的 (a) 要大，所以这些 sad 的渔夫安排在后面的任意位置都可以，而渔夫 (i) 则必须被安排在当前序列中的第一个空位，这样才能保证 (i) 渔夫是 happy 的，否则如果前面有空位，那后来填进去的渔夫一定会使得渔夫
(i) 不 happy

(dp) 转移方程为：
$$dp[i] = sum_{0}^{px[i]}A(n - 2 - px[j], px[i] - px[j] - 1)$$

最后要特别注意，因为最大的渔夫必须是 happy 的，所以第 (n - 1) 小的渔夫一定要满足 (a[n - 1] <= frac{a[n]}{2}), 也就是 (px[n] = n - 1)
否则的话方案数一定为 (0)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;

const int maxn = 5010;
const int M = 998244353;

int n, m;
int a[maxn], dp[maxn], fac[maxn], ifac[maxn], px[maxn];

int sta[maxn], p[maxn], tail = 0;

int qsm(int i, int po){
	int res = 1;
	while(po){
		if(po & 1) res = 1ll * res * i % M;
		po >>= 1;
		i = 1ll * i * i % M;
	} 
	return res;
}

int A(int n, int m){
	if(m > n) return 0;
	return 1ll * fac[n] * ifac[n - m] % M;
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	fac[0] = 1; 
	for(int i = 1 ; i <= 5000 ; ++i) fac[i] = 1ll * fac[i - 1] * i % M;
	ifac[5000] = qsm(fac[5000], M - 2);
	for(int i = 4999 ; i >= 0 ; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % M;
	
	n = read();
	for(int i = 1 ; i <= n ; ++i) a[i] = read();
	
	sort(a + 1, a + 1 + n);
	
	int top = 0;
	for(int i = 1 ; i <= n ; ++i){
		while(a[top + 1] * 2 <= a[i]) ++top;
		px[i] = top; 
	}
	
	dp[0] = 1, px[0] = -1;
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 0 ; j <= px[i] ; ++j){
			dp[i] = (dp[i] + 1ll * dp[j] * A(n - 2 - px[j], px[i] - px[j] - 1) % M) % M;
		}
	}
	
	if(px[n] == n - 1) printf("%d
", dp[n]); // 最大的数必须开心 
	else printf("0
");
	
	return 0;
}