菜王的 blog

完全不需要提前计算贡献啊，为什么题解都是。

原题面中的 $k$ 在这里用 $m$ 表示。

将 $a$ 排序后，显然有 DP 设 $f_{i, j, k}$ 为考虑前 $i$ 个，有 $j$ 组还没有放 $\max$，当前不和谐度之和为 $k$ 的方案数。转移是显然的，每次加入一个数考虑它是新一组的唯一元素 / 新一组的 $\min$ / 之前一组的中间值 / 之前一组的 $\max$ 四种情况：

$f_{i, j, k} = (j + 1)(f_{i - 1, j, k} + f_{i - 1, j + 1, k - a_i}) + f_{i - 1, j - 1, k + a_i}$

直接这样转移，第三维中途可能会很小 / 很大，所以时间复杂度为 $O(n^2\sum a_i)$。

但我们可以剪枝啊！有很多状态最终是无法转移到最终合法状态的。

考虑一个状态 $f_{i, j, k}$ 能转移到的最小不和谐度。显然，将 $a_i$ 后面的 $j$ 个作前面 $j$ 组的 $\max$，剩下的单独成组即可。令 $sm = \sum_{p = i + 1}^{i + j} a_p$，即最终不和谐度为 $k + sm$。则 $k + sm \le m$ 时，$f_{i, j, k}$ 才是有用的。

将不等式变形，得到 $k \le m - sm$，这是 $k$ 的一个上界。而 $k$ 的下界 $lk$ 显然是 $-\sum_{p = i - j + 1}^i a_p$（在前 $i$ 个中选最后 $j$ 个作为 $\min$，剩下的单独成组），又因为 $a$ 的单调性，所以 $-sm \le lk \le k \le m - sm$（前面 $j$ 个加起来肯定小于等于后面 $j$ 个），则 $m - sm - lk \le m - sm + sm = m$，对于一对 $i, j$，有用的 $k$ 只有 $O(m)$ 个。

每次只转移有用的 $k$，时间复杂度即可减为 $O(n^2m)$。main code：

for (int i = 1;i <= n;i ++){swap(f0, f1);
	for (int j = 0;j <= i && j <= n - i;j ++){
		int le = sm[i - j] - sm[i], ri = m - sm[i + j] + sm[i];
		for (int k = le;k <= ri;k ++){f1[j][k] = 0;
			add(f1[j][k], (j + 1ll) * f0[j][k] % mod);
			if (j && k + a[i] <= m) add(f1[j][k], f0[j - 1][k + a[i]]);
			if (j < n) add(f1[j][k], (j + 1ll) * f0[j + 1][k - a[i]] % mod);
			if (i == n && !j) add(ans, f1[j][k]);
		}
	}
}