CF2063F1 F1. Counting Is Not Fun (Easy Version)题解

F1. Counting Is Not Fun (Easy Version)

题目翻译

​ 题目给我们一个数字n，代表一个有着n个好对的括号序列，一个好对（i, j) (i < j) 满足s[i] == ‘(‘, s[j] == ‘)’同时去掉i，j两个字符，区间内剩余的子串是一个合法的平衡括号字符串，可以证明对于一个长度位2 * n的括号序列一定有n个好对。题目依次给出n个好对，我们需要计算出前i个好对确定的情况下有多少种符号要求的合法括号字符串（i从0到n）。

思路

​ 首先我们根据题目的定义我们发现对于一个好对[l, r]其中l - 1， r - 1可以填任何合法的括号序列，所以我们需要预处理出长度x时的合法括号序列数，这可以通过dp[len] [diff]来n ^ 2的dp处理出来，状态表示长度为len时平衡度为diff的括号序列数量。然后考虑如何根据确定了的好对来计算可能的括号序列种类。我们发现一个好对就可以把其包含区间的种类给算出来，并且按照定义好对不会相交，只有可能包含，包含时我们可以用来填的空要是还没有确定的，也就是去掉包含的好对长度，于是对于前i个，我们可以通过维护左端点第一关键，右端点第二关键，有序的好对前缀，来O（n）的计算出每个好对还可以填写的空，结合dp[len] [0]相乘计数即可，最后乘上剩余所有没填的空的贡献即可。

代码

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
constexpr ll mod = 998244353;
int N = 5000;

std::vector<std::vector<int>> dp(2 * N + 1, std::vector<int>(2 * N + 1, 0));

void init(){
    dp[0][0] = 1;
    for(int i = 1; i <= 2 * N; i++){
        for(int j = 0; j <= i; j++){
            if(j > 0)
                dp[i][j] = (1LL * dp[i][j] + dp[i - 1][j - 1]) % mod;
            if(j < N)
                dp[i][j] = (1LL * dp[i - 1][j + 1] + dp[i][j]) % mod;
        }
    }
}

void solve(){
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> cur(n + 1);
    for(int i = 1; i <= n; i++)
        std::cin >> cur[i].ff >> cur[i].ss;

    std::vector<ll> res;
    res.push_back(dp[2 * n][0]);

    std::vector<int> occur(n + 1, 0);
    cur[0].ff = 0;
    cur[0].ss = 2 * n + 1;

    std::vector<int> qu;

    for(int i = 1; i <= n; i++){
        int ind = -1;
        for(int j = 0; j < i - 1; j++){
            if(cur[qu[j]].ff <= cur[i].ff || (cur[qu[j]].ff == cur[i].ff && cur[qu[j]].ss <= cur[i].ss)){
                ind = j;
            }
            else
                break;
        }
        //std::cerr << i << space << ind << endl;

        std::vector<int> now;
        for(int j = 0; j <= ind; j++)
            now.push_back(qu[j]);
        now.push_back(i);
        for(int j = ind + 1; j < qu.size(); j++)
            now.push_back(qu[j]);
        qu = now;
    
        // for(int j = 0; j < qu.size(); j++)
        //     std::cerr << qu[j] << sendl[j == qu.size() - 1];
        std::stack<int> stk;
        for(int j = 0; j <= i; j++)
            occur[j] = 0;

        stk.push(0);
        for(auto ind : qu){
            int l = cur[ind].ff;
            int r = cur[ind].ss;
            while(cur[stk.top()].ss < r)
                stk.pop();
            occur[stk.top()] += r - l + 1;
            stk.push(ind);
        }
        
        ll ans = 1;
        for(int j = 1; j <= i; j++){
            ll use = 2 + occur[j];
            ll last = (cur[j].ss - cur[j].ff + 1) - use;
            ans = (ans * dp[last][0]) % mod;
        }
        ll last = 2 * n - occur[0];
        ans = (ans * dp[last][0]) % mod;

        res.push_back(ans);
    }
    for(int i = 0; i < res.size(); i++)
        std::cout << res[i] << sendl[i == res.size() - 1];
}