题解：AT_arc227_f [ARC227F] Erase and Raise

wzc6666 · 2026-11-10 16:14:58 · 题解

发现最终的序列一定不会有一样的（我去不早说）。

那么能通过最终序列还原出有几个 0 吗？假设我们不考虑两个相邻 0 消，那么就是：

两个 0 相当于区间加操作，用最少的区间加维护数列，这个是经典结论了，加 cnt 是因为得从原本的 0 加上去。

值域，相邻位置，差的绝对值，直接想到连续段 dp，设 dp_{i,j} 为总和为 i 有 j 个空的方案数，为啥这么设呢？

首先 a_0 和 a_{cnt + 1} 都是固定的 0，那么相当于两侧边界已经有了，由段数变成维护空数显然更直观。

每次值域移动 1 都有 di = i + 2j，这个参照 P9197，我们直接写一下转移。

• 单开一段：dp_{di + 1,j + 1} += dp_{i,j} \times j。
• 延长一段：dp_{di+1,j} += dp_{i,j} \times j \times 2。
• 合并两段：dp_{di+1,j-1}+=dp_{i,j} \times j。
• 啥也不干：dp_{di,j}+=dp_{i,j}。

前三个很好理解就是板子，啥也不干的转移式也好说，那么问题来了，为什么能啥也不干？

假设最终序列为 0,2,4,1，发现把 3 跳过了，如果不加入啥也不干转移的话，那么它就和 0,2,3,1 无法区分了。

那么，为什么不用单开一维值域呢？显然开出来肯定没毛病能做，但是太慢了，回忆完全背包，是不是也没开“这个物品取了几个”这一维。

道理是一样的，关心的只有贡献和段数，而不关心去了多少，就像是背包只考虑重量不考虑几个物品一样。

既然 di 是递增的，我们这么转移肯定没问题。

统计答案就要看两个 0 消了，发现最后的奇偶性和 n 相同就计入答案，空数 j 要为 0。

你可能会想，这二维 dp 时间复杂度不是 n^2 的吗，实际不是，一直加段会快速增加贡献，再减回来还要再次贡献，所以第二维本质是 \sqrt n + O(1) 的。

给了 5 秒还说啥了。

接下来写完发现过不了，手玩发现最终序列含有 0 的都没考虑，那么初状态就不能仅仅设 dp_{0,1} = 1 了，我们分讨一下。

• 空序列：dp_{0,0} = 1。
• 没有 0：dp_{0,1} = 1。
• 单个 0：dp_{1,0} = 1。

所以做完了，时间复杂度 O(n\sqrt n)。

代码由人类生成仅供参考。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010,M = 450;
const int mod = 998244353;
int n;
int dp[N][M];
int ans = 0;
signed main(){
    cin>>n;
    dp[0][0] = 1;//空 
    dp[0][1] = 1;//无0 
    dp[1][0] = 1;//单个0 
    dp[1][2] = 1;//0在中间 
    dp[1][1] = 2;//0在两边 
    for(int i = 0;i<n;i++){
        for(int j = 1;j<M - 1;j++){
            int di = i + 2 * j;
            if(di > n)break;
            dp[di + 1][j + 1] = (dp[di + 1][j + 1] + dp[i][j] * j % mod) % mod;//单开一段 
            dp[di + 1][j] = (dp[di + 1][j] + dp[i][j] * j * 2 % mod) % mod;//延长一段 
            dp[di + 1][j - 1] = (dp[di + 1][j - 1] + dp[i][j] * j % mod) % mod;//合并两段 
            dp[di][j] = (dp[di][j] + dp[i][j]) % mod;//啥也不干 
        }
    }
    for(int i = 0;i<=n;i++){
        if(i % 2 != n % 2)continue;//奇偶性相同 
        ans = (ans + dp[i][0]) % mod;
    }
    cout<<ans<<"\n";
    return 0;
}