题解：AT_agc079_a [AGC079A] Tree Contraction Sequence

· · 题解

设 a_i 表示点 i+1 是第几个被操作的，显然 a 是一个 1 到 n-1 的排列。

设 fa_i 为点 i+1 的父亲，一个 a 合法当且仅当对所有 i\in[1,n-1]，都有 a_i=\max_{j=fa_i}^{i}a_j。

:::info[证明] 用 b_i 表示 a_{i-1}，P_i 为 i 的父亲。
在任意时刻，一个点的序列都是递增的，不然它接到 1 的序列后就寄了。

对点 i，若存在点 j\in(fa_{i-1},i]，j 比 i 晚操作，操作 i 后，i 父亲的序列就会缺一个 j。你发现 j 补不上去，就寄了，所以这个条件是必要的。

操作 u 时，设 f 为 u 当前的父亲，v 为 f 序列的结尾，w 为 f 的儿子，且是 v 的祖先。显然有 w\le v,b_w<b_u,b_v<b_u。反证，假设 v>u。

若 w>u，根据条件有 b_w>b_u，与 b_w<b_u 矛盾。
若 w<u，则 w<u<v，w 到 v 的路径上一定存在一个点 y 使得 u\in(P_y,y)。你发现 b_u>b_y，与条件矛盾。
也就是说，v<u，那么这个条件就是充分的。 :::

从左往右扫描 i，不断地令 fa_i\gets\min_{j=fa_i}^{i}fa_j。你发现这样做的好处是对 a 的限制不变，且所有 [fa_i,i] 区间要么不交要么有包含关系。

对区间 [fa_i,i]，定义它的权值为 n-a_i+1，现在的限制是对每个区间，它的权值都要小于它所有子区间的权值。

你发现这是一个树的拓扑序状物，根据经典结论，答案就是 \frac{(n-1)!}{\prod_{i=1}^{n-1}siz_i}。其中 siz_i 表示 [fa_i,i] 的子树大小，也就是 i-fa_i+1。

场上比较唐，写了个树状数组查询后缀最小值，实际上用并查集就行了。 

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
#define ll long long
#define ull unsigned ll
#define lid (id << 1)
#define rid (id << 1 | 1)
typedef pair<int, int> pii;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
namespace Pinball{
    const int P = 998244353;
    int n, fac[N], inv[N];
    int qpow(int a, int b){
        int r = 1;
        while (b){
            if (b & 1) r = (ll)r * a % P;
            a = (ll)a * a % P;
            b >>= 1;
        }
        return r;
    }
    int a[N], tr[N];
    void add(int p, int k){
        for (;p;p -= p & -p) tr[p] = min(tr[p], k);
    }
    int query(int p){
        int r = 1e9;
        for (;p <= n;p += p & -p) r = min(r, tr[p]);
        return r;
    }
    int ans;
    void Purgatory(){
        cin >> n;
        --n;
        for (int i = 1;i <= n;i++) tr[i] = 1e9;
        for (int i = 1;i <= n;i++){
            cin >> a[i];
            add(i, a[i]);
            while (1){
                int t = query(a[i]);
                if (t == a[i]) break;
                a[i] = t;
            }
            add(i, a[i]);
        }
        ans = 1;
        for (int i = 1;i <= n;i++) ans = (ll)ans * i % P;
        for (int i = 1;i <= n;i++) ans = (ll)ans * qpow(i - a[i] + 1, P - 2) % P;
        cout << ans << '\n';
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--) Pinball::Purgatory();
    return 0;
}