CF1988F Heartbeat 题解

题意简述

对于一个 $1 \sim n$ 的排列，定义：

• 前缀最大值：位置 $i$ 满足 $u_i > u_j$ 对所有 $j < i$ 成立。
• 后缀最大值：位置 $i$ 满足 $u_i > u_j$ 对所有 $j > i$ 成立。
• 上升点：位置 $i\ (i>1)$ 满足 $u_i > u_{i-1}$。

给定数组 $a[1..n],\ b[1..n],\ c[0..n-1]$，一个排列的代价定义为 $a_x \cdot b_y \cdot c_z$，其中 $x,y,z$ 分别为该排列的前缀最大值个数、后缀最大值个数、上升点个数。

对每个 $k = 1,2,\ldots,n$，求 $1 \sim k$ 的所有排列的代价之和，对 $998\,244\,353$ 取模。

$n \le 700$，各数组元素 $< 998\,244\,353$。

---

核心思路：按最大值 $n$ 分割

前缀最大值和后缀最大值无法在同一个 DP 中同时维护，但观察发现：

• 最大值 $n$ 一定是前缀最大值，也一定是后缀最大值。
• $n$ 左侧只有前缀最大值，$n$ 右侧只有后缀最大值。

因此分别计算 $n$ 左侧（前缀部分）和 $n$ 右侧（后缀部分）的贡献，最后拼接。问题分成三步：

1. 对前缀部分，计算 $f_{i,u}$：用 $i$ 个数组成有 $u$ 个上升点的所有排列中，$a_x$（$x=$ 前缀最大值个数，含 $n$）的总和。
2. 对后缀部分，计算 $g_{j,v}$：用 $j$ 个数组成有 $v$ 个上升点的所有排列中，$b_y$（$y=$ 后缀最大值个数，含 $n$）的总和。
3. 通过 $f,g$ 与组合数合并出最终答案。

---

第一部分：前缀 DP

DP 设计

采用“从大到小插入”的构造方式。想象我们在构造 $n$ 左侧的序列，数字从 $n-1$ 向下依次插入。全局最大值 $n$ 始终位于最右端作为“边界”。

设 $dp_{i,j,k}$ 表示：已插入 $i$ 个数（来自 $\{n-1,\dots,n-i\}$），含 $n$ 在内的前缀最大值个数为 $j$，序列内部的上升对数为 $k$ 的方案数。

初始状态：$i=0$ 时，只有 $n$ 自身，$j=1,\ k=0$。实际实现中直接处理 $f_{0,0}=a_1$ 和 $g_{0,0}=b_1$，并将首个元素插入作为 $dp_{1,2,0}=1$。

转移

插入当前最小的数时，有三种位置选择：

插入位置	前缀最大值 $j$	上升对数 $k$	方案乘数
插入到最开头	$j+1$	$k+1$	$1$
插入到一个下降对中间（$l > r$）	$j$		$(i-1)-k$
插入到一个上升对中间或末尾		$k$	$1+k$

解释：

• 开头插入：新数成为第一个元素，自动成为前缀最大值；且新数 < 原首元素，产生一个上升对。
• 插入下降对中间：原有 $l > r$ 变为 $l > \text{新数} < r$，新增一个上升对（新数 $< r$），前缀最大值不变。
• 插入上升对中间或末尾：原有 $l < r$ 变为 $l > \text{新数} < r$，消失一个上升对同时新增一个，净变化 $0$；前缀最大值不变。

其中 $(i-1)-k$ 为当前序列中下降对的个数，$1+k$ 为上升对个数 $+1$（末尾位置）。

转移均为主动转移，复杂度 $O(n^3)$。

计算 $f$ 与 $g$

完成 $dp$ 后：

$$f_{i,k} = \sum_{j=1}^{i+1} dp_{i,j,k} \cdot a_j$$

$g$ 的处理有一个巧妙转换：将后缀部分左右翻转，则原后缀最大值变为前缀最大值，上升对变为下降对。因此：

$$g_{i,\ (i-1)-k} = \sum_{j=1}^{i+1} dp_{i,j,k} \cdot b_j $$

即后缀部分 $i$ 个数、$v$ 个上升点的情况，对应翻转后 $i$ 个数、$(i-1)-v$ 个上升点的 $dp$ 状态。

---

第二部分：合并答案

最终的排列结构为：左侧 $i$ 个数（上升点 $u$，前缀最大值含 $n$），最大值 $n$，右侧 $j$ 个数（上升点 $v$，后缀最大值含 $n$）。总长度 $s = i + j + 1$。

总上升点数 $z = u + v + [i \neq 0]$（左侧非空时，左部分末元素 $< n$ 产生一个额外上升；$n$ 到右部分首元素是下降，不计入）。

答案为：

$$ans_s = \sum_{\substack{i+j+1=s \\ u+v \le n}} f_{i,u} \cdot c_{u+v+[i\neq0]} \cdot g_{j,v} \cdot \binom{i+j}{i} $$

其中 $\binom{i+j}{i}$ 表示从 $n-1$ 个数中选出 $i$ 个放入左侧的方案数。

合并过程

先对每个 $i,v$ 合并 $u$ 维度：

$$iv_{i,v} = \sum_{u} f_{i,u} \cdot c_{u+v+[i\neq0]} $$

再对每个 $i,j$ 合并 $v$ 维度：

$$ij_{i,j} = \sum_{v} iv_{i,v} \cdot g_{j,v}$$

最后乘组合数贡献到答案：

$$ans_{i+j+1} \mathrel{+}= ij_{i,j} \cdot \binom{i+j}{i} $$

每次合并都是 $O(n^3)$，总复杂度 $O(n^3)$。

---

复杂度

• DP 状态 $O(n^3)$，转移 $O(1)$。
• 合并答案 $O(n^3)$。
• 组合数预处理 $O(n^2)$。

$n \le 700$ 时 $n^3 \approx 3.4 \times 10^8$，常数较小，可通过。

---

参考代码

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

constexpr int N = 700;
constexpr int P = 998244353;

int C[N + 1][N + 1];
int n, a[N + 1], b[N + 1], c[N];
int dp[2][N + 1][N + 1];
int f[N + 1][N + 1], g[N + 1][N + 1];
int iv[N + 1][N + 1], ij[N + 1][N + 1];
int ans[N + 1];

inline void init() {
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
        }
}

inline void get_fg() {
    memset(dp, 0, sizeof dp);
    f[0][0] = a[1];
    g[0][0] = b[1];
    dp[1][2][0] = 1;
    for (int i = 1; i < n; i++) {
        memset(dp[i & 1 ^ 1], 0, sizeof dp[i & 1 ^ 1]);
        auto &from = dp[i & 1];
        auto &to = dp[i & 1 ^ 1];
        for (int j = 1; j <= i + 1; j++)
            for (int k = 0; k <= i; k++)
                if (from[j][k]) {
                    if (i < n - 1) {
                        // 插在开头
                        int add = from[j][k];
                        (to[j + 1][k + 1] += add) %= P;
                        // 插在下降对中间
                        add = from[j][k] * 1LL * ((i - 1) - k) % P;
                        (to[j][k + 1] += add) %= P;
                        // 插在末尾或上升对中间
                        add = from[j][k] * 1LL * (1 + k) % P;
                        (to[j][k] += add) %= P;
                    }
                    (f[i][k] += from[j][k] * 1LL * a[j] % P) %= P;
                    (g[i][(i - 1) - k] += from[j][k] * 1LL * b[j] % P) %= P;
                }
    }
}

inline void get_ans() {
    for (int i = 0; i < n; i++)
        for (int u = 0; u <= n; u++)
            for (int v = 0; u + v <= n; v++)
                (iv[i][v] += f[i][u] * 1LL * c[u + v + (i != 0)] % P) %= P;
    for (int i = 0; i < n; i++)
        for (int v = 0; v <= n; v++)
            for (int j = 0; j < n; j++)
                (ij[i][j] += iv[i][v] * 1LL * g[j][v] % P) %= P;
    for (int i = 0; i < n; i++)
        for (int j = 0; i + j < n; j++)
            (ans[i + j + 1] += ij[i][j] * 1LL * C[i + j][i] % P) %= P;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    init();
    get_fg();
    get_ans();
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
    return 0;
}