Solution:
First, we consider what options are available to meet the conditions.
Obviously [0, 1, 2, 3, 4, 5] is eligible, because for any i, x[i]-MEX(x[1],..., x[i])=-1. Similarly, [0, 1, 2, 3, 4, 5, 5, ... ,5] also meets the conditions.
The total number of all possibilities of this construction is actually clear: we use dp[x] to represent the possible number of subsequences starting from 0 and ending with x.
So obviously for each i, dp[x[i]]+=dp[x[i]]+dp[x[i]-1]. In other words, for the current x[i], either the previous number is also equal to x[i], or the previous number is equal to x[i]-1
At the same time, we noticed another construction method, such as: [0, 1, 2, 3, 5]. At this time x[i]-MEX(x[1],..., x[i])=5-4=1 (when i=5).
A special feature of this construction method is that the further expansion of this construction has certain restrictions.
First of all [0, 1, 2, 3, 5, 4] is not eligible, because when i=6, x[i]-MEX(x[1],..., x[i])=4- 6=-2. Therefore, it is not difficult to find that there are actually only two expansion methods: 1. [0, 1, 2, 3, 5, 3, 5, 3, ...]; 2. [0, 1, 2, 3, 5, 5 , 5,...].
So for this construction, we use end[x] to represent the total number of all possibilities starting from 0 and ending with x (not including x+2).
So for each i, end[x[i]-2]+=end[x[i]-2]+dp[x[i]-2]. In other words, take x[i]=5 as an example, or add a new 5 after [0,1,2,3,5,3,...] (end[x[i]-2] , Because all the previous cases can continue a 5), or it is the first time to add 5 after [0,1,2,3] (dp[x[i]-2], because it is the first time, 0-3 Is continuous).
At the same time end[x[i]]+=end[x[i]]. In other words, still taking 5 as an example, if it was [0,1,2,3,4,5,7,5,7,...] before, we can add another 5.
The final result is equal to the sum of all end[i] and dp[i].
Code:
Java
C++
