CF1608F MEX counting 口胡

CodeForces 1608F

显然，题目拆掉绝对值，题目变成了对于 \(a\) 的前缀的 \(mex\) 有区间限制

考虑 DP ，设 \(dp[i][mex][j]\) 表示前 \(i\) 位 ，\(Mex(a_1,a_2,\dots,a_i)=mex\) ，有 \(j\) 位数 \(>mex\) 的方案数

之所以这样设，是因为我们关心 \(mex\) ，并且不关心 \(>mex\) 的具体是那些数

容易列出方程：

\[dp[i][mex][j]= \begin{cases}dp[i-1][mex-1][j]+dp[i][mex-1][j+1]\times(j+1)\\ dp[i-1][mex][j-1]+dp[i-1][mex][j]\times(mex+j) \end{cases} \]

注意，要先进行第一行的转移，因为第一行涉及到用 \(dp[i]\) 转移 \(dp[i]\) ，否则会算错

最后的答案就是 \(\sum P_{n-mex}^j dp[n][mex][j]\) ，那个排列数是为了得到 \(>mex\) 的 \(j\) 个数的实际方案

\(dp\) 第一维显然可以滚掉，那么时间复杂度就是 \(n^2k\) ，空间 \(nk\)

这道题卡常，蒟蒻被卡爆了，这里给出 @GreenSnake 的代码

#include
 
using namespace std;
typedef long long ll;
 
const int N = 2000 + 5, K = 100 + 5, Mod = 998244353;
int n = 0, k = 0, b[N] = {}, m = 0, p = 0;
int dp[2][K][N] = {}, g[N] = {}, ans = 0;
 
int main(){
	scanf("%d %d", &n, &k);
	for(int i = 1 ; i <= n ; ++ i) scanf("%d", &b[i]);
	dp[0][k][0] = 1;
	for(int i = 1 ; i <= n ; ++ i){
		p = p ^ 1;
		for(int j = 0 ; j <= i + 1 ; ++ j) g[j] = 0;
		for(int mex = m ; mex <= min(b[i] + k, i) ; ++ mex) for(int j = 0 ; j <= i - mex ; ++ j){
			g[j] = 1ll * g[j + 1] * (j + 1) % Mod;
			if(mex > m && mex - 1 <= b[i - 1] + k) g[j] = (g[j] + dp[p ^ 1][mex - 1 - b[i - 1] + k][j]) % Mod;
			if(mex >= b[i] - k){
				dp[p][mex - b[i] + k][j] = g[j];
				if(mex <= b[i - 1] + k && mex < i){
					if(j + mex < i) dp[p][mex - b[i] + k][j] = (dp[p][mex - b[i] + k][j] + 1ll * dp[p ^ 1][mex - b[i - 1] + k][j] * (j + mex)) % Mod;
					if(j && j + mex - 1 < i) dp[p][mex - b[i] + k][j] = (dp[p][mex - b[i] + k][j] + dp[p ^ 1][mex - b[i - 1] + k][j - 1]) % Mod;
				}
			}
		}
		m = max(m, b[i] - k);
	}
	for(int j = 0 ; j <= n ; ++ j) g[j] = 0;
	for(int mex = m ; mex <= n ; ++ mex) for(int j = 0 ; j <= n - mex ; ++ j){
		if(mex <= b[n] + k) g[j] = (g[j] + dp[p][mex - b[n] + k][j]) % Mod;
		if(j) g[j - 1] = 1ll * g[j] * (n - mex) % Mod;
		else ans = (ans + g[j]) % Mod;
	}
	printf("%d", ans);
	return 0;
}