题解：P16256 [DSTOI Round 0] 相思若循 3

Cqou · 2026-08-12 15:04:51 · 题解

考虑序列 u 在位置 i 和 i+1 之间发生翻转，意味着 x_i \ge y_i 和 x_{i+1} \ge y_{i+1} 一真一假。

记 X = x_i，Y = x_{i+1}，分两种情况讨论。

::::info[情况一]{open} 若 X = Y，说明 a_{i+1} 没刷新最大值。此时翻转只能是 y_i \le X 且 y_{i+1} > X，即前 i 个还压得住，第 i+1 个压不住了。前 i 个位置需要从 1 \sim X 中选且必含 X，方案数为 \frac{X!}{(X-i)!}；第 i+1 个位置得选一个大于 X 的数，有 n-X 种选法；剩下 n-i-1 个位置随便排，有 (n-i-1)! 种。因此方案数为 \frac{X!}{(X-i)!} \cdot (n-X) \cdot (n-i-1)!。

::::

::::info[情况二]{open} 若 X < Y，说明 a_{i+1} 刷新最大值。翻转有两种互斥的情形：

• 前面压得住，后面压不住：y_i \le X 且 y_{i+1} > Y。前 i 个最大值 \le X，第 i+1 个得飙到 > Y。方案数为 \frac{X!}{(X-i)!} \cdot (n-Y) \cdot (n-i-1)!。
• 前面压不住，后面压住了：y_i > X 且 y_{i+1} \le Y。前 i 个最大值在 (X, Y] 之间，第 i+1 个 \le Y。方案数为 \frac{Y!}{(Y-i-1)!} \cdot (n-i-1)!。

两部分相加，合并得 (n-i-1)! \left[ \frac{X!}{(X-i)!}(n+i-2Y) + \frac{Y!}{(Y-i-1)!} \right]。

::::

对每个 i 从 1 到 n-1，根据 X 和 Y 的关系套用上面两个公式之一，算出该位置的贡献，全部累加起来就是所有 b 对应的 z 之和。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long pw(long long b, long long e, long long mod) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> fac(n + 1), ifac(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[n] = pw(fac[n], MOD - 2, MOD);
    for (int i = n; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;

    vector<int> x(n + 1);
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > mx) mx = a[i];
        x[i] = mx;
    }

    long long ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        int X = x[i], Y = x[i + 1];
        long long t;
        if (X == Y) {
            t = fac[X] * ifac[X - i] % MOD * (n - X) % MOD * fac[n - i - 1] % MOD;
        } else {
            long long c1 = (n + i - 2LL * Y) % MOD;
            if (c1 < 0) c1 += MOD;
            long long t1 = fac[X] * ifac[X - i] % MOD * c1 % MOD;
            long long t2 = fac[Y] * ifac[Y - i - 1] % MOD;
            t = fac[n - i - 1] * ((t1 + t2) % MOD) % MOD;
        }
        ans += t;
        if (ans >= MOD) ans -= MOD;
    }

    cout << ans << "\n";
    return 0;
}
::::