题解：CF1988F Heartbeat

猜测目标

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

本题解参考官方做法。

一看到数据范围，容易想到我们需要

\mathcal O(n^3)

或

\mathcal O(n^2 \log n)

的时间复杂度去解决这个问题。

不过看看时限，还是

\mathcal O(n^3)

的概率大一点。

设计状态

首先，这一道题和全排列有关，容易想到肯定有一个

i

表示将

1 \sim i

这些数字排列。

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

$dp_{i,j,k,x}$ 表示 $1 \sim i$ 的排列， $j$ 个上升点对， $k$ 个前缀最大值， $x$ 个后缀最大值的方案数。

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

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

$f_{i,j,k}$ 表示 $1 \sim i$ 的排列， $j$ 个上升点对， $k$ 个前缀最大值的方案数。
$g_{i,j,k}$ 表示 $1 \sim i$ 的排列， $j$ 个上升点对， $k$ 个后缀最大值的方案数。

因为我们拆开了

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}

，那应该很明显了吧。

代码：

CPP

#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;
}

题解：CF1988F Heartbeat

文章操作

猜测目标

设计状态

转移方程

统计答案

相关推荐

评论

题解：CF1988F Heartbeat