CF1437F. Emotional Fishermen

发表于 | 阅读数

将元素重新排列，询问不出现$y\leq 2x\leq 4y$, $y$=之前最大值。

显排个序，假设确定一个最大元素的时候，$\leq \frac{a_i}{2}$已经可以随便选择了，因为范围$[L,R]$只会往左边移动。

$dp[i]$表示选择$a_i$的方案数。

转移的时候
$dp[i]=\sum dp[j]\times A_{n - 2 - mx[j]}^{mx[i] - mx[j] - 1}$

$mx[i]$表示最大的$j$满足$2\times a[j]\leq a[i]$

思考这个$DP$,当$dp[j]$,有$mx[j]+1$个元素已经排好的时候，将$a_i$放在$a_j$的下一个位置。那么剩下就是$(n-2-mx[j])$个位置，随机放置$mx[i] - mx[j] - 1$。

由于这样$dp$,前缀最大值的顺序是一定，就可以保证不重不漏了。

代码 
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 998244353;

namespace math
{
    int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
    int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
    int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    int qpow(int a, int x, int mo)
    {
        int res = 1;
        while (x)
        {
            if (x & 1)
                res = 1ll * res * a % mod;
            a = 1ll * a * a % mod;
            x >>= 1;
        }
        return res;
    }
    int Fac[N], invFac[N];
    void Finit(int n)
    {
        Fac[0] = 1;
        invFac[0] = 1;
        for (int i = 1; i <= n; i++)
            Fac[i] = 1ll * Fac[i - 1] * i % mod;
        invFac[n] = qpow(Fac[n], mod - 2, mod);
        for (int i = n - 1; i >= 1; i--)
            invFac[i] = 1ll * invFac[i + 1] * (i + 1) % mod;
    }
    int C(int n, int m)
    {
        if (m == 0)
            return 1;
        if (n < m || m < 0)
            return 0;

        return (int)(1ll * Fac[n] * invFac[m] % mod * invFac[n - m] % mod);
    }
    int A(int n, int m)
    {
        // if (m == 0)
        //     return 1;
        if (n < 0 || m < 0 || m > n)
            return 0;
        return (1ll * Fac[n] * invFac[n - m] % mod);
    }

} // namespace math

using namespace math;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int main()
{
    int n = read();
    Finit(n);
    vector<int> a(n + 1), mx(n + 1, n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = read();
    sort(1 + a.begin(), a.end());

    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (2 * a[j] <= a[i])
                mx[i] = j;
        }
    }
    mx[0] = -1;
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (2 * a[j] <= a[i])
                dp[i] = inc(dp[i], 1ll * dp[j] * A(n - 2 - mx[j], mx[i] - mx[j] - 1) % mod);
        }
    }

    cout << (mx[n] == n - 1 ? dp[n] : 0) << endl;
}