Educational Codeforces Round 118 MEX Sequences 题解 (Java/C++)

题解

首先我们考虑有那些选择方式可以满足条件。

显然[0, 1, 2, 3, 4, 5]是符合条件的，因为对于任意的i，x[i]-MEX(x[1],..., x[i])=-1。
同理，[0, 1, 2, 3, 4, 5, 5, ... ,5]也是满足条件的。
这种构造的总可能数其实是比较明确的：我们用dp[x]表示从0开始以x结尾的子序列的可能数。
于是显然对于每一个i，dp[x[i]]+=dp[x[i]]+dp[x[i]-1]。也就是说，对于当前的x[i]，要么其前一位也等于x[i]，要么前一位等于x[i]-1。

同时我们注意到另外一种构造，形如：[0, 1, 2, 3, 5]。此时x[i]-MEX(x[1],..., x[i])=5-4=1（当i=5时）。
而这一种构造的一个特殊之处在于，这种构造的进一步扩展有一定的限制。
首先[0, 1, 2, 3, 5, 4]是不符合条件的，因为i=6时，x[i]-MEX(x[1],..., x[i])=4-6=-2。
因此不难发现，其实只有两种扩展方式：1. [0, 1, 2, 3, 5, 3, 5, 3, ...]； 2. [0, 1, 2, 3, 5, 5, 5,...]。
于是对于这种构造，我们用end[x]表示，从0开始以x结尾（不包括x+2）的可能数。
于是对于每一个i，end[x[i]-2]+=end[x[i]-2]+dp[x[i]-2]。也就是说，以x[i]=5为例，要么是在[0,1,2,3,5,3,...]后面添加一个新的5（end[x[i]-2]，因为前面的所有情况都可以延续一个5），要么是[0,1,2,3]后面第一次添加5（dp[x[i]-2]，因为是第一次，0-3是连续的）。
同时end[x[i]]+=end[x[i]]。也就是说，依然以5为例，如果之前是[0,1,2,3,4,5,7,5,7,...]，我们再添加一个5。

最后结果等于所有end[i]和dp[i]的和。

代码

Java

C++