AT_arc227_f [ARC227F] Erase and Raise 题解

先找不变量，可以发现进行一次操作后数组的长度会减少 $2$，数组相邻元素差的绝对值最多增加 $1$。因此记 $f(a)$ 表示 $a$ 序列的长度加上 $a$ 序列相邻元素差的绝对值的和，则所有合法的序列均满足 $f(a)\le n$。然后分析奇偶性可得合法序列的长度和 $n$ 奇偶性相同，最终不能操作说明合法序列内任意两个元素的值都互不相同。然后考虑充分性。把最终得到的序列倒着操作，每次选一端区间值减 $1$ 然后在区间的两侧插入两个 $0$，一定可以退回 $n$ 个 $0$ 组成的序列。具体来说，每次选择当前序列的一个连续极长全正整数段，把这个段内所有元素都减去 $1$ 然后在这个段左右两侧补上 $0$，序列的 $f$ 值一定不会变化。最终会得到一个长度为 $m$ 的全 $0$ 序列，且满足 $n\equiv m\pmod 2\land m\le n$。然后考虑长度为 $n$ 的全 $0$ 序列每次可以删除一对相邻的 $0$ 让序列的长度减少 $2$，因此确实可以从长度为 $m$ 的全 $0$ 序列操作到长度为 $n$ 的全 $0$ 序列上。于是证明了上面给的三个条件是题目中序列合法的充要条件。

然后考虑怎么对这个东西做计数。要计数的是长度为 $m$（$n\equiv m\pmod 2\land m\le n$）的，满足 $\sum\limits_{i=0}^m|b_{i+1}-b_i|+m\le n$ 的序列 $b$ 的数量（这里认为 $b_0=b_{m+1}=0$）。套路的把所有元素的值从小到大插入到 dp 数组中，设 $f_{i,j,k}$ 表示当前从小到大插入到了 $i$ 数，当前有 $j$ 个值 $>i$ 的段，已经产生的 $f$ 值是 $k$，有多少种合法的序列。考虑当前值的位置：

• 不选择 $i$，则所有的大数段都不会发生变化。
• 选择 $i$，则 $i$ 值一定落在 $j$ 个连续大数段之一中，然后分类这个位置对大数段数量的影响：
  • 若插入的位置两侧都有大数，则连续大数段的数量会增加 $1$，两边都有比当前数要大的数，分裂成了两个块，得到了两种新的结构，因此方案数为 $2j$。
  • 若插入的位置两侧都没有大数，则连续大数段的数量会减少 $1$，方案数显然为 $j$。
  • 若插入的位置两侧中恰有一侧有大数，则连续大数段的数量不变，大数可以出现在当前数的左侧，也可以出现在当前数的右侧，因此方案数为 $2j$。

然后可以发现转移的过程和 $i$ 维度没有任何关联，而且随着 $i$ 的增大 $k$ 也会同样增大，因此可以直接消去 $i$ 这个 dp 维度，把所有原 dp 状态中 $i$ 不同但是 $j,k$ 相同的状态直接合并成同一个状态转移即可。然后再分析一下可以发现 $k$ 维度的上界只有 $O(\sqrt n)$ 级别，因此直接转移时间复杂度为 $O(n\sqrt n)$，可以通过该题。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int f[N][510];

inline void sol([[maybe_unused]]int __testcase_id, [[maybe_unused]]int __testcase_sum) {
    int n; cin >> n; f[0][0] = 1;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= 500; ++j)
            if (i + j + j <= n) {
                f[i + j + j + 1][j] = (f[i + j + j + 1][j] + f[i][j] * j * 2 % mod) % mod, f[i + j + j + 1][j + 1] = (f[i + j + j + 1][j + 1] + f[i][j]) % mod;
                if (j) f[i + j + j][j] = (f[i + j + j][j] + f[i][j]) % mod, f[i + j + j + 1][j - 1] = (f[i + j + j + 1][j - 1] + f[i][j] * j % mod * (j - 1) % mod) % mod;
            }
    int res = 0;
    for (int i = n; i > 0; i -= 2) res = (res + f[i][1]) % mod;
    if (n % 2 == 0) res = (res + 1) % mod;
    cout << res << '\n';
}

} // namespace lowspeed_song