I admit that AGC061C is too hard for me, and I don't even understand its official editorial. Today I see a Luogu blog with a very genius and clear idea on this problem. I learned a lot from it, and I would like to share it to you now. The writer of this blog is possibly Little09, but I am not quite sure.
Part1: Problem Statement and Constraints
There are N
At the entrance, there's a list of visitors to put their names in. Each customer will write down their name next in the list exactly once, either when they arrive or when they leave. How many different orders of names can there be in the end? Find the count modulo 998244353
Constraints:
⋅1≤N≤500000
⋅1≤Ai≤Bi≤2N
⋅Ai<Ai+1(1≤i≤N−1)
⋅Bi<Bi+1(1≤i≤N−1)
⋅Ai≠Bj(i≠j)
⋅All values in the input are integers
Part2: Idea of the blog
The complexity of the algorithm in the blog is O(N)
Consider two dynamic programming tables named f
f(i)(1≤i≤n)
g(i)(1≤i≤n)
The blog defines c(i)
c(i):=max{j|Aj<Bi}
Obviously i∈{j|Aj<Bi}
First, we consider f(i)
f(i)=f(i+1)+g(i)−g(c(i))
Second, we consider g(i)
Pj
(1)Do these Pj
(2)Do these Pj
(3)How to calculate the size of Pj
Therefore,
g(i)=c(i)∑j=i+1g(j)+f(c(i)+1)
Although we consider f
Part3: Implementation details
(1) You can use two pointers to calculate c
(2) To make the computation of g
(3) The original blog considers two cases: c(i)=i
(4) In the original blog Little09 calculates from n
Part4: What I have learned
(1) The most important idea in counting is dividing into non-overlapping sets whose unions are the whole set. Besides, the counting of each set should be much simpler.
(2) The most important thing of dp is defining states.
(3) Bijections are really important in combinatorics. For example, the Dyck path.
(4) Achieving (1) and (2) requires high IQ and talent. For example, the definition of f
Part5: The last
If you have any questions, please don't hesitate to ask me. It is beneficial for both of us. For you, I might resolve your confusion. For me, I can check whether I make a typo in the blog or not and whether I really understand this blog or not.