首先我们考虑对序列从小到大排序，那么一个集合的极差就可以用两端点之差来描述。
贡献显然是可以拆的，那么我们从左往右做动态规划，经典方式是维护一个“未闭合”的集合数量（即未维护右端点贡献），状态 $f(i,j,k)$ 表示维护到 $i$，$j$ 个区间未闭合，总贡献为 $k$。
转移分四类来做：
- 与一个未闭合区间合并并闭合
- 与一个未闭合区间合并但不闭合
- 新开一个区间且闭合
- 新开一个区间但不闭合
状态转移方程即为：
$$
\begin{aligned}
f(i,j,k) &= (j+1) \cdot f(i-1,j+1,k-a(i)) \\
&+ j \cdot f(i-1,j,k) \\
&+ f(i-1,j,k) \\
&+ f(i-1,j-1,k+a(i))
\end{aligned}
$$
但是由于最后一位的值域是 $\sum a_i$ 级别的，所以时间复杂度上不可取。
考虑到最后答案是 $\sum_{k=0}^m f(n,0,k)$，所以我们希望最后一维的值域在 $m$ 级别。
注意到如果我们保证最后一维转移递增，那么我们就达到了这个目的。
考虑不同的拆贡献方案，可以做一个差分再区间和起来，这样我们保证转移的最后一维递增。
设 $d=a(i) - a(i-1)$。
类似的转移：
$$
\begin{aligned}
f(i,j,k) &= (j+1) \cdot f(i-1,j+1,k-(j+1) \cdot d) \\
&+ j \cdot f(i-1,j,k-j \cdot d) \\
&+ f(i-1,j,k-j \cdot d) \\
&+ f(i-1,j-1,k-(j-1) \cdot d)
\end{aligned}
$$
滚动数组。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200;
const int maxm=1000;
const int mod=998244353;
int n,m;
int a[maxn+5];
int f[2][maxn+5][maxm+5];
int ans;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
f[0][0][0]=1;
for(int i=1;i<=n;i++){
int d=a[i]-a[i-1];
for(int j=0;j<=i;j++){
for(int k=0;k<=m;k++){
f[1][j][k]=0;
if(k-(j+1)*d>=0&&j+1<=i-1){
f[1][j][k]=(f[1][j][k]+(j+1)*f[0][j+1][k-(j+1)*d])%mod;
}
if(k-j*d>=0){
f[1][j][k]=(f[1][j][k]+j*f[0][j][k-j*d])%mod;
f[1][j][k]=(f[1][j][k]+f[0][j][k-j*d])%mod;
}
if(k-(j-1)*d>=0&&j-1>=0){
f[1][j][k]=(f[1][j][k]+f[0][j-1][k-(j-1)*d])%mod;
}
if(i==n&&j==0) ans=(ans+f[1][j][k])%mod;
}
}
swap(f[0],f[1]);
}
printf("%lld",ans);
return 0;
}
|