题解：CF1988F Heartbeat

STDLRZ · 2025-05-31 12:33:52 · 题解

猜测目标

提前声明：本篇文章比较偏向小白~~因为本作者是蒟蒻。~~

本题解参考官方做法。

一看到数据范围，容易想到我们需要 \mathcal O(n^3) 或 \mathcal O(n^2 \log n) 的时间复杂度去解决这个问题。

不过看看时限，还是 \mathcal O(n^3) 的概率大一点。

设计状态

首先，这一道题和全排列有关，容易想到肯定有一个 i 表示将 1 \sim i 这些数字排列。

但是如果我们如果这么定义：

显然在没有得到任何性质之前，这根本转移不了啊。

发现问题是无法同时维护前缀最大值和后缀最大值的个数，于是我们只能含泪去掉一个，于是定义：

因为我们拆开了 dp 数组中的 k,x，但是很明显，在一个全排列中总有一对 (k,x) 是不可能出现的。

比如当 i=3 时，(1,1) 是不可能出现的。

因为如果你的 k=1，那么 3 就必须在第一个位置；如果你的 x=1，那么 3 就必须在第三个位置。矛盾了。

也就是说，k,x 是有隐含的联系的，我们这么拆掉，只是为了方便转移，后面统计答案时要想办法将这两者之间的联系给消掉，否则答案很难统计~~或者根本统计不了~~，这个到时候再说吧，先放着。

转移方程

我们先考虑怎么转移。

首先，容易发现 f 和 g 是对称的。

具体来说，g_{i,i-j-1,k}=f_{i,j,k}。

为什么呢？考虑将 f 每一个方案都给表示成一个数组。

然后，将这个数组倒过来，这样前缀最大值就变成后缀最大值啦。

考虑上升点对，很明显原来的上升点对变成了下降点对，下降点对变成了上升点对。

但是因为总共只有 i-1 个点对，所以翻过来之后就是 i-j-1。

所以，我们只要把 f 求出来就行了。

怎么从 i \to i+1 呢？我们只要将原来 1 \sim i 的排列变成 2 \sim i+1 的排列，然后再插入一个 1 就好啦。

至于为什么不能直接插入 i+1，等会会有解释。

讨论：

将 1 插入到 j 个上升点对之间。
将 1 插入到第一个位置。
将 1 插入到最后一个位置。
其他情况。

对于第一种情况，虽然 1 把这个上升点对拆散了，但是 1 和原先上升点对的后面那个数结合起来，又组成了一个新的上升点对，所以最后没变。

所以则有：

dp_{i,j,k} \times j \to dp_{i+1,j,k}

当然，在这个情况下，1 肯定不会插入到第一个位置（否则那就不叫之间了），插入到第一个位置的情况要另外讨论，因为会新增一个前缀最大值。

对于第二种情况，1 仍然会和后面的一个数构成一个新的上升点对，并且新增一个前缀最大值。

所以则有：

dp_{i,j,k} \to dp_{i+1,j+1,k+1}

对于第三种情况，既不会产生新的上升点对，也不会产生新的前缀最大值。

所以则有：

dp_{i,j,k} \to dp_{i+1,j,k}

对于第四种情况，则会产生一个新的上升点对，不会产生新的前缀最大值。

所以则有：

dp_{i,j,k} \times (i-j-1) \to dp_{i+1,j+1,k}

将所有情况讨论完后，总结一下，有如下转移：

\begin{equation*} \begin{cases} dp_{i,j,k} \times (j+1) \to dp_{i+1,j,k} \\ dp_{i,j,k} \to dp_{i+1,j+1,k+1} \\ dp_{i,j,k} \times (i-j-1) \to dp_{i+1,j+1,k}\\ \end{cases} \end{equation*}

对不能插入 i+1 的一个解释：

首先，对于上升点对来说，插入 i+1 是可计算的。
但是，对于前缀最大值来说，如果在某个位置插入了 i+1，那么就会使得这个位置的后面，原先是前缀最大值的将不是前缀最大值，但是我们无法统计一个位置后面的前缀最大值个数，自然就不能插入 i+1 啦。
就算方法改了之后还是可以插入 i+1，那我估计转移的复杂度应该不是 \mathcal O(1) 啦，估计最后优化不到正解的程度，而且不如插入 1 简单。
所以这里不讨论插入 i+1 的转移，而且我估计以当前状态应该是很难转移了。

至于空间复杂度，很明显，因为所有式子都是 i \to i+1，所以直接滚动即可。

统计答案

首先，如讲述“状态定义”标题时已经有提到过，我们要让 k,x 之间的联系断开。

我们想想，前缀最大值和后缀最大值，怎样才能断开呢？

其实，都是最大值嘛，那我们就像前文对不能插入 i+1 的解释一样，插入一个比整个序列更大的数，那不就将 k,x 的联系给切开了嘛？

所以，我们枚举全排列 1 \sim n 中 n 的位置，这样 k,x 就在 n 位置断开了，就无关了。

于是，答案如下：

ans_n= \sum_{p=1}^n \sum_{i=1}^{p-1} \sum_{j=1}^{n-p} \sum_{x=1}^{p-1} \sum_{y=1}^{n-p} C_{n-1}^{p-1} \cdot f_{p-1,x,i} \cdot g_{n-p,y,j} \cdot a_{i+1} \cdot b_{j+1} \cdot c_{x+y+[p>1]}

其中，p 枚举的是 n 所在的位置，i,j 分别枚举的是前缀最大值和后缀最大值个数，x,y 分别枚举的是 n 左边的上升点对个数和 n 右边的上升点对个数。

然后至于 C_{n-1}^{p-1}，就是分开之后在 1 \sim n-1 这些数中选 p-1 个数作为左边的部分。

为什么呢？因为我们其实要的只是相对顺序。

至于上升点对，如果 p>1，那么他就会和前一个数组成一个没有被统计的上升点对，但是 p=1 没有前一个数，所以无法组成上升点对。

如果真就这样统计的话，总时间复杂度为 \mathcal O(n^6)，完全不可接受。

但是，我们观察到有一些式子的部分只与部分变量有关，于是转换，得：

ans_n= \sum_{p=1}^n \sum_{x=1}^{p-1} \sum_{y=1}^{n-p} \sum_{i=1}^{p-1} \sum_{j=1}^{n-p} C_{n-1}^{p-1} \cdot (f_{p-1,x,i} \cdot a_{i+1}) \cdot (g_{n-p,y,j} \cdot b_{j+1}) \cdot c_{x+y+[p>1]}

将 f_{p-1,x,i} \cdot a_{i+1},g_{n-p,y,j} \cdot b_{j+1},c_{x+y+[p>1]},C_{n-1}^{p-1} 提出去，得：

ans_n= \sum_{p=1}^n (C_{n-1}^{p-1} \times \sum_{x=1}^{p-1} \sum_{y=1}^{n-p} (c_{x+y+[p>1]} \times (\sum_{i=1}^{p-1} f_{p-1,x,i} \cdot a_{i+1}) \times (\sum_{j=1}^{n-p} g_{n-p,y,j} \cdot b_{j+1})))

于是，我们设：

r_{p,x}=\sum_{i=1}^p f_{p,x,i} \cdot a_{i+1} \\ s_{p,y}=\sum_{j=1}^p g_{p,y,j} \cdot b_{j+1}

这两个式子的预处理复杂度均为 \mathcal O(n^3)。

带入原式，得：

ans_n= \sum_{p=1}^n (C_{n-1}^{p-1} \times \sum_{x=1}^{p-1} \sum_{y=1}^{n-p} (c_{x+y+[p>1]} \times r_{p-1,x} \times s_{n-p,y}))

此时时间复杂度被降为 \mathcal O(n^4)，但还需要再降一个 n 才能通过本题。

发现此时只要预处理 c_{x+y+[p>1]} \times r_{p-1,x} 就好了。

为什么不能预处理 r_{p-1,x} \times s_{n-p,y} 呢？

因为 c_{x+y+[p>1]} 涉及到了 3 个变量，不管你这个预处理是枚举了 p 好，还是枚举了 x,y 好，最后你为了计算 c_{x+y+[p>1]} 还得枚举，还要去重，跟没有预处理一样。

所以，这里预处理的本质是什么？

就是通过变换 \sum 之间的位置，然后将和预处理无关的式子给提出去，只有将所有和预处理无关的式子全部提出去之后，我们才能预处理成功。

否则，如果你提不出去（就像 c_{x+y+[p>1]}），那你 r_{p-1,x} \times s_{n-p,y} 也就休想预处理啦。

这样我们就从题目里面又获取到了一个知识啦。

那为什么不能预处理 c_{x+y+[p>1]} \times s_{n-p,y} 呢？

因为你计算 ans 的时候，n 也要枚举的啊。这样，如果将 n 也给算一个变量，那么这个式子就有 4 个变量了，预处理复杂度就升到了 \mathcal O(n^4) 了，不如不预处理。

于是，我们还是将上面 ans_n 的式子变一下，得：

ans_n= \sum_{p=1}^n (C_{n-1}^{p-1} \times \sum_{y=1}^{n-p} \sum_{x=1}^{p-1} (c_{x+y+[p>1]} \times r_{p-1,x} \times s_{n-p,y}))

将 s_{n-p,y} 提出去，得：

ans_n= \sum_{p=1}^n (C_{n-1}^{p-1} \times \sum_{y=1}^{n-p} (s_{n-p,y} \times \sum_{x=1}^{p-1} (c_{x+y+[p>1]} \times r_{p-1,x})))

这样，我们就可以愉快的预处理 \sum_{x=1}^{p-1} (c_{x+y+[p>1]} \times r_{p-1,x}) 了。

设：

t_{p,y}=\sum_{x=1}^p (c_{x+y+[p>0]} \times r_{p,x})

如果不理解，可以将 p'=p-1 带入，得：

t_{p',y}=\sum_{x=1}^{p'} (c_{x+y+[p'>0]} \times r_{p',x}) \\ t_{p-1,y}=\sum_{x=1}^{p-1} (c_{x+y+[p-1>0]} \times r_{p-1,x})

当然，逆着推过来可以知道是否正确，那怎么顺着推过来呢？

令 p'=p-1，先书写原来的式子：

t_{p-1,y}=\sum_{x=1}^{p-1} (c_{x+y+[p>1]} \times r_{p-1,x})

为了让 c_{x+y+[p>1]} 能变得和 p' 有关，于是我们将 p>1 移一下项，得到 p-1>0，这样就可以转换为 p'>0 了。~~所以数学还是很重要滴。~~

这样，我们将 t_{p,y} 带入原式，得：

ans_n= \sum_{p=1}^n (C_{n-1}^{p-1} \times \sum_{y=1}^{n-p} (s_{n-p,y} \times t_{p-1,y}))

这样，再预处理 C_{n-1}^{p-1}，这道题就彻底被解决了。

再考虑一下初始值吧，考虑到 p-1 可能为 0，所以令 dp_{0,0,0}=dp_{1,0,1}=1。

很明显，在没有数的时候，肯定啥贡献都没有啊。

至于 dp_{1,0,1}，那应该很明显了吧。

代码：

#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define j0 j_0
#define j1 j_1
#define jn j_n
#define k0 k_0
#define k1 k_1
#define d0 d_0
#define d1 d_1
#define LL long long
#define LD long double
#define Big __int128
#define STR string
#define US unsigned
#define ZPB push_back
#define ZPF push_front
#define PPB pop_back
#define PPF pop_front
#define next NXTNXT
#define UPB upper_bound
#define LWB lower_bound
#define mem(x,val) memset(x,val,sizeof(x))
using namespace std;
int n,a[710],b[710],c[710],dp[2][710][710],r[710][710],s[710][710],t[710][710],C[710][710];
const int mod=998244353;
void added(int &a,int b) {a+=b;if(a>=mod) a-=mod;return ;}
int mul(int a,int b) {return ((LL)a*b)%mod;}
int add(int a,int b) {a+=b;if(a>=mod) a-=mod;return a;}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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]; 
    for(int i=0;i<=n;++i){
        C[i][0]=1;
        for(int j=1;j<=i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
    }
    dp[0][0][0]=dp[1][0][1]=1,r[0][0]=a[1],s[0][0]=b[1];
    for(int i=1;i<=n;++i){ 
        int now=i&1,nxt=now^1;
        mem(dp[nxt],0);
        for(int x=0;x<i;++x)
            for(int j=1;j<=i;++j)
                added(r[i][x],mul(dp[now][x][j],a[j+1])),
                added(s[i][x],mul(dp[now][i-x-1][j],b[j+1]));
        for(int j=0;j<i;++j)
            for(int k=1;k<=i;++k){
                added(dp[nxt][j][k],mul(dp[now][j][k],j+1)),
                added(dp[nxt][j+1][k+1],dp[now][j][k]),
                added(dp[nxt][j+1][k],mul(dp[now][j][k],i-j-1));
            }
    }
    for(int p=0;p<=n;++p){
        for(int y=0;y<=n;++y)
            for(int x=0;x<=p;++x) added(t[p][y],mul(c[x+y+(p>0)],r[p][x]));
    }
//  for(int i=0;i<=n;++i)
//      for(int j=0;j<=n;++j)
//              cout<<"r["<<i<<"]["<<j<<"]="<<r[i][j]<<"\n",
//              cout<<"s["<<i<<"]["<<j<<"]="<<s[i][j]<<"\n",
//              cout<<"t["<<i<<"]["<<j<<"]="<<t[i][j]<<"\n";
    for(int i=1;i<=n;++i){
        int ans=0;
        for(int p=1;p<=i;++p){
            int res=0;
            for(int y=0;y<=i-p;++y) added(res,mul(s[i-p][y],t[p-1][y]))/*,cerr<<"s="<<s[i-p][y]<<" t="<<t[p-1][y]<<"\n"*/; 
            added(ans,mul(res,C[i-1][p-1]));
        }
        cout<<ans<<" ";
    }
    cout<<"\n"; 
    return 0;
}