CF1608F MEX counting

题目链接

感觉是真的 👍。

首先肯定是个计数。

简单的转化一下题目中给的条件，将 ai​a_i​ 转化成前 i​i​ 个数的 MEX​MEX​ 在 [max⁡(0,ai−k),min⁡(n,ai+k)]​[\max(0,a_i-k),\min(n,a_i+k)]​ 内，不难发现这个跟原题是等价的。

发现这个 MEXMEX 是不好处理的，因为我加一个数 MEXMEX 可能不止加一，这就不好直接记进状态里面，要记也就只能状压，这显然是不可行的。

但是我们发现 {0,1,2,3,5}\left\{0,1,2,3,5\right\} 和 {0,1,2,3,5,6,7}\left\{0,1,2,3,5,6,7\right\} 的 MEXMEX 是一样的，也就是说 MEXMEX 后面的数其实是不用管的，这不影响当前的 MEXMEX，我们只需要记录下来 MEXMEX 后面有多少种（“种”的原因是集合不可重，所以不是“个”）数，我们在 MEXMEX 变化的时候再考虑后面的数怎么填，这样我们就能把状态放到 dpdp 的里面了，考虑设 fi,j,kf_{i,j,k} 表示考虑到了第 ii 个位置，当前的 MEXMEX 是 jj，jj 后面还有 kk 种数的方案数，考虑转移。

fi+1,j,k←j×fi,j,k 第 i+1 位填的是一个小于 j 的数fi+1,j,k←k×fi,j,k 第 i+1 位填的是一个大于 j 且已经在前面出现过的数fi+1,j,k+1←fi,j,k 第 i+1 位填的是一个大于 j 且没有在前面出现过的数fi+1,t,k−(t−j−1)←fi,j,k×k!(k−(t−j−1))!,t∈[max⁡(j+1,li+1),ri+1] 第 i+1 位填的是一个等于 j 的数\begin{aligned} &f_{i+1,j,k} \leftarrow j\times f_{i,j,k} \ 第\ i+1\ 位填的是一个小于\ j\ 的数 \\ &f_{i+1,j,k} \leftarrow k\times f_{i,j,k} \ 第\ i+1\ 位填的是一个大于\ j\ 且已经在前面出现过的数 \\ &f_{i+1,j,k+1} \leftarrow f_{i,j,k} \ 第\ i+1\ 位填的是一个大于\ j\ 且没有在前面出现过的数 \\ &f_{i+1,t,k-(t-j-1)} \leftarrow f_{i,j,k}\times \frac{k!}{(k-(t-j-1))!}, t \in [\max(j+1,l_{i+1}),r_{i+1}] \ 第\ i+1\ 位填的是一个等于\ j\ 的数 \end{aligned}

其中第四个转移的排列数的含义就是我有 kk 要让 [j+1,t−1][j+1,t-1] 都有数的方案数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=n;i++){
	int x; rd(x);
	l[i]=max(x-m,0),r[i]=min(n,x+m);
}
f[0][0][0]=1;
for(int i=0;i<n;i++){
	for(int j=l[i];j<=r[i];j++){
		for(int k=0;k<=n;k++){
			f[i+1][j][k]=(f[i+1][j][k]+1ll*j*f[i][j][k])%P;
			f[i+1][j][k]=(f[i+1][j][k]+1ll*k*f[i][j][k])%P;
			f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%P;
			for(int t=max(j+1,l[i+1]);t<=r[i+1];t++) f[i+1][t][k-(t-j-1)]=(f[i+1][t][k-(t-j-1)]+1ll*f[i][j][k]*fac[k]%P*inv[k-(t-j-1)])%P;
		}
	}
}
int ans=0;
for(int i=l[n];i<=r[n];i++){
	for(int j=0;j<=n;j++) ans=(ans+f[n][i][j]*A(n-i,j));
}
wt('\n',ans);

时间复杂度 O(n2k2)O(n^2k^2)。

这是过不了的，考虑继续优化，考虑把这个柿子化的简单一点。

有一个神奇的东西：
假设你有一个 dpdp：fi=∑jfj×j!i!f_i=\frac{\sum\limits_j f_j\times j!}{i!}，你可以设一个 gi=fi×i!g_i=f_i\times i!，这样转移就变成了 gi=∑jfj×j!i!×i!=∑jgjg_i=\frac{\sum\limits_j f_j\times j!}{i!}\times i!=\sum\limits_{j} g_j。

根据上面所说的，我们把我们这道题的 dpdp 状态改成：fi,j,kf_{i,j,k} 表示考虑到了第 ii 个位置，当前的 MEXMEX 是 jj，jj 后面还有 kk 种数的方案数乘上 k!k!，这样代码就变成这样了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
f[0][0][0]=1;
for(int i=0;i<n;i++){
	for(int j=l[i];j<=r[i];j++){
		for(int k=0;k<=n;k++){
			f[i+1][j][k]=(f[i+1][j][k]+1ll*j*f[i][j][k])%P;
			f[i+1][j][k]=(f[i+1][j][k]+1ll*k*f[i][j][k])%P;
			f[i+1][j][k+1]=(f[i+1][j][k+1]+1ll*(k+1)*f[i][j][k])%P;
			for(int t=max(j+1,l[i+1]);t<=r[i+1];t++) f[i+1][t][k-(t-j-1)]=(f[i+1][t][k-(t-j-1)]+f[i][j][k])%P;
		}
	}
}
int ans=0;
for(int i=l[n];i<=r[n];i++){
	for(int j=0;j<=n;j++) ans=(ans+1ll*f[n][i][j]*inv[j]%P*A(n-i,j))%P;
}
wt('\n',ans);

现在我们的柿子就很明了了，转移只跟 ff 有关了，这玩意很像前缀和优化 dpdp，但是你发现在转移的时候有两维都在变化，这是不太好做的。

然后就有了一个非常神奇的东西：

我们把这句话拉出来：

1
for(int t=max(j+1,l[i+1]);t<=r[i+1];t++) f[i+1][t][k-(t-j-1)]=(f[i+1][t][k-(t-j-1)]+f[i][j][k])%P;

我们把 f[i+1][t][k-(t-j-1)] 的后两维相加，即 t+k−(t−j−1)=k+j+1t+k-(t-j-1)=k+j+1，这跟 f[i][j][k] 的后两维相加正好差 1！

这样我们就可以把状态改成 fi,j+k,kf_{i,j+k,k} 表示考虑到了第 ii 个位置，当前的 MEXMEX 是 jj，jj 后面还有 kk 种数的方案数乘上 k!k!

代码：

1
2
3
4
5
6
7
8
9
10
11
f[0][0][0]=1;
for(int i=0;i<n;i++){
	for(int j=l[i];j<=r[i];j++){
		for(int k=0;k<=n;k++){
			f[i+1][j+k][k]=(f[i+1][j+k][k]+1ll*j*f[i][j+k][k])%P;
			f[i+1][j+k][k]=(f[i+1][j+k][k]+1ll*k*f[i][j+k][k])%P;
			f[i+1][j+k+1][k+1]=(f[i+1][j+k+1][k+1]+1ll*(k+1)*f[i][j+k][k])%P;
			for(int t=max(j+1,l[i+1]);t<=r[i+1];t++) f[i+1][j+k+1][k-(t-j-1)]=(f[i+1][j+k+1][k-(t-j-1)]+f[i][j+k][k])%P;
		}
	}
}

现在我们就可以直接加上前缀和了！

注意我们的空间是 O(n3)O(n^3) 的，所以还要加上一个滚动数组。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
namespace IO{
	const int L=1e6+7;
	char buf[L],*SS,*TT;
	#define gc() ((SS==TT&&(SS=buf)==(TT=buf+fread(buf,1,L,stdin)))?EOF:*SS++)
	inline void rstr(char &c){ c=gc(); while(c==' '||c=='\n'||c=='\r') c=gc();  }
	inline int rstr(char s[]){
		char c=gc(); int len=0;
		while(c==' '||c=='\n') c=gc();
		while(c!=' '&&c!='\n'&&c!='\r'&&c!=EOF) s[len++]=c,c=gc();
		return len;
	}
	inline int rstr(string &s){
		char c=gc(); int len=0; s="";
		while(c==' '||c=='\n') c=gc();
		while(c!=' '&&c!='\n'&&c!='\r'&&c!=EOF) s+=c,len++,c=gc();
		return len;
	}
	template<typename T> inline void rd(T &x){
		x=0; bool f=0; char c=gc();
		while(c<'0'||c>'9') f|=c=='-',c=gc();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=gc();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){ rd(x),rd(args...); }
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		if(c!=EOF) putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T x,Args ...args){ wt(c,x),wt(c,args...); }
	template<typename T,typename ...Args> inline void wt(char s,char c,T x,Args ...args){ wt(c,x),wt(c,args...),putchar(s); }
};
using IO::rd;
using IO::rstr;
using IO::wt;
typedef long long LL;
const int P=998244353;
const int N=2007;
int n,m;
int l[N],r[N];
int fac[N],inv[N];
int f[2][N<<1][N];
int sum[N<<1][N];
inline LL qmi(LL a,LL b,LL P){
	LL ans=1,x=a;
	while(b){
		if(b&1) ans=ans*x%P;
		x=x*x%P,b>>=1;
	}
	return ans;
}
inline void init(int n){
	for(int i=fac[0]=inv[0]=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%P;
	inv[n]=qmi(fac[n],P-2,P);
	for(int i=n-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%P;
}
inline LL A(int n,int m){
	if(n<0||m<0||n<m) return 0;
	return 1ll*fac[n]*inv[n-m]%P;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	rd(n,m);
	init(n);
	for(int i=1;i<=n;i++){
		int x; rd(x);
		l[i]=max(x-m,0),r[i]=min(n,x+m);
	}
	f[0][0][0]=1;
	for(int i=0;i<n;i++){
		for(int k=0;k<=i;k++){
			for(int j=l[i];j<=r[i];j++){
				f[(i+1)&1][j+k][k]=(f[(i+1)&1][j+k][k]+1ll*(j+k)*f[i&1][j+k][k])%P;
				f[(i+1)&1][j+k+1][k+1]=(f[(i+1)&1][j+k+1][k+1]+1ll*(k+1)*f[i&1][j+k][k])%P;
				sum[j+k][k]=((k?sum[j+k][k-1]:0)+f[i&1][j+k][k])%P;
			}
		}
		for(int j=max(l[i],l[i+1]);j<=r[i+1];j++){
			for(int k=0;k<=i;k++){
				if(!(j+k)||min(n,j+k-1-l[i])<0) continue;
				f[(i+1)&1][j+k][k]=((f[(i+1)&1][j+k][k]+sum[j+k-1][min(n,j+k-1-l[i])]-(k?sum[j+k-1][k-1]:0))%P+P)%P;
			}
		}
		for(int k=0;k<=i;k++){
			for(int j=l[i];j<=r[i];j++) sum[j+k][k]=f[i&1][j+k][k]=0;
			for(int j=l[i-1];j<=r[i-1];j++) f[i&1][j+k][k]=f[i&1][j+k+1][k+1]=0;
		}
	}
	int ans=0;
	for(int i=l[n];i<=r[n];i++){
		for(int j=0;j<=n;j++) ans=(ans+1ll*f[n&1][i+j][j]*inv[j]%P*A(n-i,j))%P;
	}
	wt('\n',ans);
	return 0;
}

因为我一开始考虑的那种 dpdp 转移方式不能前缀和优化，得填表刷表之间换一换，所以代码写的非常抽象（

题解
#计数 #dp
CF1608F MEX counting
http://lnyxqwq.github.io/2023/09/13/CF1608F MEX counting/
作者
lnyx
发布于
2023年9月13日
许可协议