ABC457F

Register_int · 2026-05-09 21:35:19 · 题解

有意思的。

发现我们比较关心最大值和次大值（废话）。不妨设 dp_{i,j} 表示 p_{i\sim n} 中，值域为 n-i+1，最大值在 j 的方案数。有转移：

• 若 d_i=d_{i+1}
  • 我可以选择插入一个不为最大或次大值的数，所有 dp 值以 n-i-1 的系数转移到自己。
  • 如果之前的最大值在 i+d_i，那么我可以选择：
  • 顶掉最大值，转移到 dp_{i,i}。
  • 顶掉次大值，转移到 dp_{i,i+d_i}。
• 否则，最大值位置只能是 i 或 i+d_i。此时由 i+d_i 转移到 dp_{i,i} 与 dp_{i,i+d_i}，其余位置全部归零。

发现操作等价于：

• 单点修改。
• 全局清空。
• 全局乘。

打个全局乘法 tag 维护即可，预处理逆元，清空时记录所有有值位置，时间复杂度 \mathcal{O}(n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int mod = 998244353;

int n, w = 1, iw = 1, d[MAXN], inv[MAXN], dp[MAXN]; vector<int> used;

int main() {
    scanf("%d", &n), dp[n] = 1, inv[1] = 1, used.reserve(n << 1);
    for (int i = 2; i <= n; i++) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i < n; i++) scanf("%d", &d[i]);
    for (int i = n - 1; i; i--) {
        int j = i + d[i], x = (ll)dp[j] * w % mod;
        if (d[i] == d[i + 1]) {
            w = (ll)w * (n - i - 1) % mod, iw = (ll)iw * inv[n - i - 1] % mod;
            int y = (ll)x * iw % mod;
            dp[i] += y, dp[i] < mod || (dp[i] -= mod);
            dp[j] += y, dp[j] < mod || (dp[j] -= mod);
        } else {
            for (int k : used) dp[k] = 0; used.clear(); 
            w = iw = 1, dp[i] = dp[j] = x;
        }
        used.emplace_back(i), used.emplace_back(j);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += dp[i], ans < mod || (ans -= mod);
    printf("%lld", (ll)ans * w % mod);
}