题解:CF1608F MEX counting
与其他题解不同,本篇题解是运用辅助数组 $g$ 来解决问题。虽然代码可能要繁琐一点,但是辅助数组的思路适用范围更广一点。
首先还是转化为前 $i$ 个数的 $mex$ 在区间 $[l_i,r_i]$ 内。
我们用 dp 数组 $f_{i,x,c}$ 表示处理到了第 $i$ 个数,当前的 mex 为 $x$,大于 mex 一共有 $c$ 个不同的数。这里我们并不关心大于 mex 的数具体是哪些,而只关心有多少个,因为只要满足大于 mex 一共有 $c$ 个不同的数,方案数都是一样的,我们只需要记录这个一样的方案数即可。注意这里钦定了这 $c$ 个数的顺序,即这 $c$ 个数是有序的(看不懂的话可以根据下面的转移来理解)。
根据定义,考虑有哪些方式能转移到 $f_{i,x,c}$:
- 这个位置填了一个之前已经出现过的数,这样的数共有 $x+c$ 个,所以转移为 $f_{i-1,x,c}*(x+c)\rightarrow f_{i,j,k}$
- 这个位置填了大于 mex 且之前没有出现过的数,那肯定是由 $f_{i,x,c-1}$ 转移过来,因为原先有 $c-1$ 个数,而数是有序的,所以新加的数与这 $c-1$ 个数的相对顺序共有 $c$ 种,所以转移为 $f_{i,x,c-1}*c\rightarrow f_{i,j,k}$
- 第三种情况也是本题的核心,即这个位置填了 mex,这样子我们并不知道有哪些状态能更新到。这时就需要辅助数组 $g$,用 $g_{i,x,c}$ 表示填到了第 $i$ 个数,小于 $x$ 的数都出现过,大于等于 $x$ 共有 $c$ 个不同的数。
这样 $g$ 怎么辅助数组 $f$ 来转移呢?具体流程为,先处理前两个转移,同时更新数组 $g$,然后再用 $g$ 来更新 $f$ 的第三个转移。
- 对于 $f$ 到 $g$ 的转移,即这个位置填了 mex,显然有 $f_{i,x,c}\rightarrow g_{i,x+1,c}$
- 对于 $g$ 到 $f$ 的转移,那么对 $g_{i,x,c}$ 分两种情况,即是否出现了 $x$ 这个数。如果出现了,那么应该转移 $g_{i,x,c}\rightarrow g_{i,x+1,c-1}$,如果没有出现,那么应该转移 $g_{i,x,c} \rightarrow f_{i,x,c}$
最后统计答案,对于 $f_{n,x,c}$,由于我们没有关心这 $c$ 个数具体是啥,所以要在剩下的 $n-x$ 个数中选 $c$ 个,因为已经钦定了 $c$ 个数的顺序,所以 $f_{n,x,c}$ 对答案的贡献为 $f_{n,x,c}*\binom{n-x}{c}$
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 2005,mod = 998244353;
int l[N],r[N],n,k;
ll C[N][N],f[2][N][N],g[N][N],ans;
void init()
{
f[0][0][0] = C[0][0] = 1;
for(int i = 1;i <= n;i++)for(int j = 0;j <= i;j++)
C[i][j] = ((j?C[i-1][j-1]:0)+C[i-1][j])%mod;
}
inline int rd()
{
char c;int f = 1;
while(!isdigit(c = getchar()))if(c=='-')f = -1;
int x = c-'0';
while(isdigit(c = getchar()))x = x*10+(c^48);
return x*f;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = rd();k = rd();init();
for(int i = 1;i <= n;i++)
{int x = rd();l[i] = max(l[i-1],x-k);r[i] = min(x+k,n);}
for(int i = 1;i <= n;i++)
{
for(int x = l[i-1];x <= r[i];x++)for(int c = 0;c <= n;c++)
g[x][c] = 0;
for(int x = l[i-1];x <= r[i-1];x++)for(int c = 0;c <= n;c++)
f[1][x][c] = f[0][x][c],f[0][x][c] = 0;
for(int x = l[i-1];x <= r[i-1];x++)for(int c = 0;c <= n;c++)//mex=x,cnt(1)=c
{
if(l[i] <= x&&x <= r[i])
{
(f[0][x][c] += f[1][x][c]*(x+c)) %= mod;
if(c)(f[0][x][c] += f[1][x][c-1]*c) %= mod;
}
(g[x+1][c] += f[1][x][c]) %= mod;
}
for(int x = l[i-1];x <= r[i];x++)for(int c = 0;c <= n;c++)
{
if(c)(g[x+1][c-1] += g[x][c]) %= mod;
if(l[i] <= x&&x <= r[i])(f[0][x][c] += g[x][c]);
}
}
for(int x = 0;x <= n;x++)for(int c = 0;c <= n;c++)
(ans += f[0][x][c]*C[n-x][c]) %= mod;
cout << ans;
return 0;
}
这种设辅助数组的思路在许多题中都可以用,值得掌握一下。
标签:题解,个数,转移,mex,数组,counting,MEX,rightarrow From: https://www.cnblogs.com/max0810/p/18327087/solution-CF1608F