题目链接：https://codeforces.com/problemset/problem/1919/E
题意
输入一个单调非减序列 \(p\)，求问有多少个序列 \(a\)，使得：
-
\(|a_i| = 1\)；
-
令 \(s_i = \sum_{j = 1}^i a_j\)，则 \(s\) 排序后与 \(p\) 相同。
序列长度不超过 \(5000\)。
题解
“排序后相同”这个条件等价于每个数的出现次数相同，也就是只要记录每个数的出现次数。为了方便分析，加入 \(p_0 = 0\)。
unordered_map<int, int> cnt;
cnt[0]++;
for (int i = 0; i < n; i++) cin >> p[i], cnt[p[i]]++;
首先显然 \(p\) 的值域是一段包含 \(0\) 的连续序列 \([-a, b]\)，可以一开始做完这个检查。
for (auto [k, v] : cnt) {
if (k < 0) {
if (!cnt.contains(k + 1)) {
cout << 0 << "\n";
return;
}
} else if (k > 0) {
if (!cnt.contains(k - 1)) {
cout << 0 << "\n";
return;
}
}
}
\(a\) 为正负一，就代表 \(s\) 相邻两项是相邻数。观察 \(s\) 的可能形态，例如 \([0, 1, 2, 1, 2, 1, 0, -1, -2, -1, 0, 1, 2, 1]\)。
用 x 轴切开这个序列，则：
-
\(s\) 被分为几段，其中除最后一段外开头和结尾均为 \(0\)，而最后一段只需要以 \(0\) 开始。我们把前一种叫做“闭区间”，后一种叫做“开区间”。（注意，当结尾为 \(0\) 时，没有最后一段开区间）
-
每一段内部要么全部大于 \(0\)，要么全部小于 \(0\)。
我们枚举开区间和闭区间各有多少段大于 \(0\)，有多少段小于 \(0\)，则可以按照“每一段内部都必须大于 \(0\)”计算，最终使用组合数合并答案即可。
Z ans = 0;
{
int closed_cnt = cnt[0] - 1;
for (int i = 0; i <= closed_cnt; i++) {
for (int c = 0; c <= 1; c++) {
ans += comb.get(closed_cnt, i) * calc(1, i, c) *
calc(-1, closed_cnt - i, 1 - c);
}
}
}
对 calc 这个子问题，考虑如何继续计算。使用一个扫描线从下往上扫描，则又有如下结论：
-
一个闭区间如果填入 \(x\) 个数，则会变为 \(x - 1\) 个闭区间。（也就是只填入一个数时，开区间在上一层消失；且至少要填入一个数）
-
一个开区间如果填入 \(x\) 个数，则会变为 \(x - 1\) 个闭区间和一个开区间。另外，如果填入 \(0\) 个数，这个开区间消失。
例如例子 \([0, 1, 2, 3, 2, 3, 2, 1, 0, 1, 2, 1]\)：
由于有两个 \(0\)，一开始有一个开区间和一个闭区间。
-
从 \(x = 0\) 向 \(x = 1\) 扫描，第一个闭区间内有两个数，仍为一个闭区间；最后一个开区间内也有两个数，变为一个闭区间和一个开区间。
-
从 \(x = 1\) 向 \(x = 2\) 扫描，第一个闭区间内有三个数，变为两个闭区间；第二个闭区间内有一个数，消失；最后一个开区间内没有数，消失。
-
从 \(x = 2\) 向 \(x = 3\) 扫描，两个闭区间内均只有一个数，均消失。
-
此时已经不存在任何区间，也不存在任何未使用的数，故这是一种可行的方案。
将状态记作 \((i, closed, open)\)，我们已经知道了状态的转移，考虑如何计数。记 \(i\) 的出现次数为 \(x\)，则：
-
若 \(open = 0\)，也就是所有的数都要填到闭区间中。每个闭区间至少要填入一个数，使用插板法知有 \(\binom{x - 1}{open - 1}\) 种方案。由于每个闭区间都使产生的新闭区间会减少一个，转移至的状态一定为 \((i + 1, x - closed, 0)\)，即 $calc(i, closed, 0) = \binom{x - 1}{open - 1} \cdot calc(i + 1, x - closed, 0) $。
-
否则，\(open = 1\)。若这个区间内不填数，则相当于 \(open = 0\) 的情况。否则，这个开区间被当做闭区间使用，相当于多出了一个闭区间的 \(open = 0\) 的情况，唯一的区别是下一层 \(open\) 也要为 \(1\)。
-
边界情况下 \(x = 0\)，此时只有 \(open = 0\) 且 \(closed \le 1\)，才是合法方案。
可以使用记忆化搜索实现。
unordered_map<i64, Z> cache;
function<Z(int, int, int)> calc = [&](int i, int closed_cnt, int open_cnt) {
if (closed_cnt < 0) return Z(0);
if (cnt[i] == 0) { return Z(closed_cnt == 0 && open_cnt <= 1); }
i64 key = (i64)i * n * 2 + closed_cnt * 2 + open_cnt;
if (cache.contains(key)) { return cache[key]; }
Z res = 0;
auto f = [&](int x, int closed_cnt, int open_cnt) -> Z {
return comb.get(x - 1, closed_cnt - 1) *
calc((i < 0) ? i - 1 : i + 1, x - closed_cnt, open_cnt);
};
int x = cnt[i];
if (open_cnt) {
res += f(x, closed_cnt + 1, 1);
res += f(x, closed_cnt, 0);
} else {
res += f(x, closed_cnt, 0);
}
return cache[key] = res;
};
但需要注意，我们这样的计算中包含了“开区间一个数都没有”的情况，这样的情况下，开区间会被分为正负各计算一次，因此需要减去这样的重复情况修正。修正后统计答案的代码如下：
Z ans = 0;
{
int closed_cnt = cnt[0] - 1;
for (int i = 0; i <= closed_cnt; i++) {
for (int c = 0; c <= 1; c++) {
ans += comb.get(closed_cnt, i) * calc(1, i, c) *
calc(-1, closed_cnt - i, 1 - c);
}
ans -= comb.get(closed_cnt, i) * calc(1, i, 0) *
calc(-1, closed_cnt - i, 0);
}
}
cout << ans << "\n";
状态数是 \(O(n^2)\) 的，因此时空复杂度均为 \(O(n^2)\)。但我的提交的时空表现都很好，不知道是不是因为数据比较松。