CF1295F Good Contest

发表于 | 阅读数

给你$n$个区间$[l_i,r_i]$,等概率选出一个数，求选完后为不严格递增序列的概率。$(n\leq 50,l_i,r_i\leq 10^9)$

最简单的$dp[i][j]$,表示选了$i$个数字,并且都大于$j$。
但是这里$j$很大,所以可以离散化，让$j$表示是数字大于等于$j$区间的数。为了保证区间各不重叠，对于一个数只可能属于一个区间，新区间要是$[l_i,r_i+1)$。

例如$[1,7],[4,9]$
新的区间就是$[1,4),[4,8),[8,9)$

然后从$1-n$枚举$i$,对于新的大区间$[l_i,r_i+1)$,坐落在里面的方案数，就是枚举离散化之后，坐落在里面的小区间$li[j]-li[j+1]$,然后枚举之前可以有多少大区间里含有这个小区间。

就变成从$len$个数里面取$t$个数，可以重复选

代码 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const int mod = 998244353;
int n, l[N], r[N], li[N], cnt;
int dp[N][N];
int qpow(int a, int b, int mo)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        b >>= 1;
    }
    return res;
}
int C(int y, int x)
{
    int ans = 1;
    for (int i = 1; i <= x; i++)
        ans = 1ll * ans * (y + 1 - i) % mod * qpow(i, mod - 2, mod) % mod;
    return ans;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &l[i], &r[i]), r[i]++, li[++cnt] = l[i], li[++cnt] = r[i];
    sort(li + 1, li + cnt + 1);
    cnt = unique(li + 1, li + cnt + 1) - li - 1;
    for (int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(li + 1, li + cnt + 1, l[i]) - (li);
        r[i] = lower_bound(li + 1, li + cnt + 1, r[i]) - (li);
    }

    for (int i = 1; i <= cnt; i++)
        dp[0][i] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = l[i]; j < r[i]; j++)
        {
            int len = li[j + 1] - li[j];
            for (int t = 1; i - t + 1 >= 1; t++)
            {
                if (!(l[i - t + 1] <= j && j < r[i - t + 1]))
                    break;
                dp[i][j] = (dp[i][j] + 1ll * dp[i - t][j + 1] * C(len + t - 1, t) % mod) % mod;
            }
        }
        for (int j = cnt - 1; j >= 1; j--)
            dp[i][j] = (dp[i][j + 1] + dp[i][j]) % mod;
    }
    int ans = dp[n][1];
    for (int i = 1; i <= n; i++)
        ans = 1ll * ans * qpow(li[r[i]] - li[l[i]], mod - 2, mod) % mod;
    printf("%d\n", ans);
    return 0;
}