[CF1613D]MEX sequences 题解

CF1613D MEX sequences

传送门

  • 思路:

(真是道好题,神犇们肯定都切掉了,但这题要是放到考场上我肯定不敢写 DP 的 QAQ)

题目范围 \(N=5\times 10^5\),又是个统计方案的题,珂以发现是道 DP 题。

联系到最长子序列问题,发现如果根据下标设计状态,时间复杂度总是 \(\operatorname{O}(N^2)\) 的。

本题答案又不具有单调性,没法用二分查找优化。

但是题中所给的值域非常小,可以根据值域求解。

然而 MEX 这个东西并不是很好处理 qwq,考虑将其设计进状态中:

设 \(F(i,k,s)\) 为序列前 \(i\) 个数中,选择了若干个数,形成了 MEX 为 \(k\) 的合法序列的方案数。

其中若子序列中的最后一个数为 \(A_j\),则

\[A_j=\left\{ \begin{matrix} k-1 \ \ \ \ \ \ \ s=0\\ k+1 \ \ \ \ \ \ \ s=1 \end{matrix} \right. \]

当 \(A_i=x\) 时,只有 \(k=x+1\),\(k=x-1\) 对应的情况会受影响,讨论一下:

  • 当 \(s=1,k=x+1\) 时,只有一种可能:

先前选出的子序列中,MEX 已经为 \(k\),且最后一个数为 \(x+2\),则当前 \(A_i\) 可选可不选。

则 \(F(i,x+1,1)=2\times F(i-1,x+1,1)\)

  • 当 \(s = 1,k = x - 1\) 时,有两种可能:
  1. 先前选出的子序列中,MEX 已经为 \(k\),且最后一个数为 \(x\),那么当前的 \(A_i\) 可以选或不选。

  2. 先前选出的子序列中,MEX 已经为 \(k\),且最后一个数为 \(x-2\),那么当前的 \(A_i\) 必须要选。

综上,\(F(i,x-1,1) = 2\times F(i-1,x-1,1) + F(i-1,x-1,0)\).

  • 当 \(s = 0,k = x + 1\) 时,有两种可能:
  1. 已选出的子序列中,MEX 已经为 \(k\),且最后一个数为 \(x+2\),那么 \(A_i\) 可选可不选。

  2. 已选出的子序列中,MEX 已经为 \(x\),且最后一个数为 \(x-1\),那么 \(A_i\) 必须选。

综上,\(F(i,x+1,0)=2\times F(i-1,x+1,0)+F(i-1,x,0)\)

  • 当 \(s=0,k=x-1\) 时,序列最大数为 \(x-2\),显然与假设矛盾,故不用讨论 \(x\)。

发现所有 \(F(i,k,s)\) 是同时由上一层 \(i-1\) 转移来的,那么可以舍弃 \(i\) 这一维,按照输入顺序转移状态。

从题目本身,我们可以发现,一个合法的子序列必然由 \(0\) 或 \(1\) 起始,但它们的初始状态不好处理。

发现无论是 \(0\) 起始还是 \(1\) 起始,都可以由 \(F(0,0)\) 转移,那么可以在一开始先设 \(F(0,0)=1\),最后减掉即可。

那么答案就是:\(\sum\limits_{i=0}^n F(i,0)+F(i,1)\)

code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500005;
typedef long long ll;
const ll mod = 998244353;
int n,x;
ll f[maxn][2],cnt;
void work() {
	scanf("%d",&n);
	for(int i = 0;i <= n;++ i)f[i][0] = f[i][1] = 0;
	cnt = -1;
	f[0][0] = 1;
	for(int i = 1;i <= n;++ i) {
		scanf("%d",&x);
		f[x + 1][0] = ((f[x + 1][0] << 1) % mod + f[x][0] % mod) % mod;
		f[x + 1][1] = (f[x + 1][1] << 1) % mod;
		if(x)f[x - 1][1] = ((f[x - 1][1] << 1) + f[x - 1][0]) % mod;
	}
	for(int i = 0;i <= n;++ i)(cnt += f[i][0] + f[i][1]) %= mod;
	printf("%lld\n",cnt);          
	return ;
}
int main() {
	int T;
	scanf("%d",&T);
	while(T --)work();
	return 0;
} 
上一篇:中国剩余定理


下一篇:java file 进度条 文件上传