CF1913D 题解

sunkuangzheng · 2023-12-19 08:41:31 · 题解

组合数学不太好做，考虑 dp。设 f_i,g_i 表示考虑序列前 i 个元素，且最后一个元素是否被删除的方案数。令 p 表示 i 前面第一个小于 a_i 的数字，有转移：

答案是 f_n + g_n。

第一个转移式子的含义是，如果第 i 个元素要被删除，那么它一定不是区间最小值，所以这个区间一定要包含小于它的数字，此时可以选择保留 p，也可以让 p 被前面更小的数字删除。第二个转移式子的含义是，第 i 个元素要保留，这个区间里它一定是最小值。上一个区间端点在 p \sim i-1 之间显然满足题意，如果 p 被删除，上一个区间端点在最后一个没有被删除的位置也合法，所以加上 f_p。

直接做是 \mathcal O(n^2) 的，对于寻找 p 显然可以单调栈，g_i 的转移有区间和， 可以简单前缀和优化。最终复杂度 \mathcal O(n)。

赛时代码，注意 f 和 g 的含义和上面相反。

/**
 *    author: sunkuangzheng
 *    created: 18.12.2023 23:06:42
**/
#include<bits/stdc++.h>
using ll = long long;
#define int long long
const int N = 5e5+5,mod = 998244353;
using namespace std;
int T,n,a[N],st[N],tp,sm[N],f[N],g[N];
void los(){
    cin >> n;tp = 0;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    f[0] = sm[0] = 1;
    for(int i = 1;i <= n;i ++){
        while(tp && a[st[tp]] > a[i]) tp --;
        int j = st[tp];if(j) g[i] = (f[j] + g[j]) % mod; else g[i] = 0;
        f[i] = (sm[i-1] - (j == 0 ? 0 : sm[j-1]) + g[j] + mod) % mod,
        sm[i] = (sm[i-1] + f[i]) % mod,st[++tp] = i;
    }cout << (f[n] + g[n]) % mod << "\n";
}signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}