Counting Cute Arrays

· · 题解

提供一种不太一样的刻画方式。

考虑限制 X_i=j 的实质，相当于：

将限制 A_u<A_v 视作 u \rightarrow v 的有向边，无解相当于有环。而环一定形如 X_i \leftarrow j_1 \leftarrow j_2 \leftarrow \dots \leftarrow j_k \leftarrow i，其中 X_i<j_1<j_2<\dots<j_k<i。进一步地，发现此时 i \rightarrow j_1 一定有直接连边，整个环可以表示为 X_i \leftarrow j \leftarrow i。这样的结构不能出现，相当于要求：对于任意 1 \le i \le n，不存在 X_i<j<i，使得 X_j<X_i，即不存在二元组 (i,j)，使得 X_j<X_i<j<i。

接下来需对这个条件计数。对每个 i 创建区间 (X_i,i)，要求所有区间要么包含要么相离。这个结构非常经典，将包含关系视作边，可建出一棵树。然后考虑刻画如下过程：维护一个栈，存放当前所有可以作为 X_i 的值；每次扫到 i，将 (X_i,i) 间的所有元素出栈，然后将 i 入栈。这个过程放到我们的树上，有性质：若 (L,R) 包含 (l,r)，那么当我们扫到 r 的时候，(l,r) 里的所有元素就出栈了，对 (L,R) 这个整体来说，我们并不关心 (l,r) 里面具体发生了什么，可以直接把它看成只有 r。

那么实际上，最终整个过程可以刻画为：若 X_i=-1，我们可以弹出任意个数的元素；否则，不能弹出任何元素。设 f_{i,j} 表示扫到 i 时栈中有 j 个元素的方案数，有转移：

f_{i,j}=\begin{cases} f_{i-1,j-1} & X_i \ne i \\ \sum\limits_{j-1 \le k \le i-1} f_{i-1,k} & X_i = i \end{cases}

自底向上对每个区间跑一遍这个 dp，最后把最上层区间拉出来再跑一遍。前缀和优化，复杂度 O(n^2)。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5010;
const int MOD = 998244353;
struct Interval{
    int l, r, ind;
    vector <int> adj;
};
bool cmp(Interval x, Interval y){
    if (x.l != y.l){
        return x.l < y.l;
    }
    return x.r > y.r;
}
void add(int &x, int y){
    x += y;
    if (x >= MOD) x -= MOD;
    return;
}
int a[MAXN], f[MAXN][MAXN], n;
int calc(vector <int> &o){
    int k = (int)o.size() - 1;
    for (int j = 1; j <= k; j++){
        f[0][j] = 0;
    }
    f[0][0] = 1;
    for (int i = 1; i <= k; i++){
        for (int j = 0; j <= k; j++){
            f[i][j] = 0;
        }
        if (o[i] == 1){
            for (int j = 1; j <= i; j++){
                f[i][j] = f[i - 1][j - 1];
            }
        }
        else{
            int sum = 0;
            for (int j = i; j >= 1; j--){
                add(sum, f[i - 1][j - 1]);
                f[i][j] = sum;
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= k; j++){
        add(ans, f[k][j]);
    }
    return ans;
}
void solve(){
    cin >> n;
    vector <Interval> s;
    int cnt = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++){
        if (a[i] >= i){
            cout << 0 << "\n";
            return;
        }
        if (a[i] != -1){
            s.push_back({a[i], i, cnt++});
        }
    }
    s.push_back({0, n + 1, cnt++});
    sort(s.begin(), s.end(), cmp);
    stack <int> st;
    for (int i = 0; i < cnt; i++){
        while (!st.empty() && s[st.top()].r < s[i].r){
            if (s[st.top()].r > s[i].l){
                cout << 0 << "\n";
                return;
            }
            st.pop();
        }
        if (!st.empty()){
            s[st.top()].adj.push_back(i);
        }
        st.push(i);
    }
    ll ans = 1;
    for (int i = 0; i < cnt; i++){
        vector <int> o;
        o.push_back(0);
        int lst = s[i].l + 1;
        for (int u : s[i].adj){
            if (s[u].l - lst + 1 < 0){
                cout << 0 << "\n";
                return;
            }
            for (int j = 1; j <= s[u].l - lst + 1; j++){
                o.push_back(0);
            }
            o.push_back(1);
            lst = s[u].r + 1;
        }
        if (s[i].r - lst < 0){
            cout << 0 << "\n";
            return;
        }
        for (int j = 1; j <= s[i].r - lst; j++){
            o.push_back(0);
        }
        ans = ans * calc(o) % MOD;
    }
    cout << ans << "\n";
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::