自动搬运

查看原文

来自洛谷，原作者为

	Lonely_NewYear 云吹开沙 火成霞

搬运于2025-08-24 22:55:06，当前版本为作者最后更新于2024-02-16 16:50:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10141 题解

题目大意

有 $n$ 个细胞排成一排，第 $i$ 个细胞大小为 $c_i$，重复 $n-1$ 次，第 $i$ 次从当前的 $n-i+1$ 个细胞中随机选出相邻的两个，并让大的吞噬小的（大小相同右吞左），被吞噬的细胞消失并将大小累加到留下的细胞上。求每个细胞活到最后的概率，对 $1e9+7$ 取模，$n\le5000$。

题目分析

对于每个细胞单独考虑，设当前考虑的细胞为 $i$，容易得到 $dp_{l,r}$ 表示 $l,r$ 区间最后活下来的是 $i$ 的概率，转移需要枚举最后一次吞噬。单个细胞复杂度 $O(n^3)$，总复杂度 $O(n^4)$，很难优化到 $O(n^2)$。

上面的做法转移的顺序是合并从小区间到大区间的顺序，正难即反，可以发现如果枚举最后一次合并，则最后留下的细胞必定来自总和较大的区间。也就是说，倒着做把合并变成分裂，每次会确定最后留下的细胞来自左侧的区间还是右侧，并将另一部分舍去不必再考虑。设 $dp_{l,r}$ 表示区间 $1,n$ 经过若干次分裂留下了区间 $l,r$ 的概率。转移时枚举 $l\le k<r$ 表示分裂出 $l,k$ 和 $k+1,r$，若 $sum_{l\sim k}>sum_{k+1\sim r}$，则将 $dp_{l,k}$ 加上 $\frac{dp_{l,r}}{r-l}$，否则让 $dp_{k+1,r}$ 加上后者。直接实现复杂度 $O(n^3)$。

继续优化，考虑所有能转移到 $dp_{l,r}$ 的区间要不然左端点是 $l$ 要不然右端点是 $r$。两部分类似，下面只讨论前者。那么如果右端点是 $k$，则要求 $sum_{l,r}>sum_{r+1,k}$，容易发现可取的 $k$ 是以 $r+1$ 为左端点的一段区间。这段区间的右端点通过对每一个 $l$ 做双指针是好求的（区间 dp 时通过枚举区间长度从大到小，枚举到的左端点为 $l$ 的区间右端点必然是递减的，随着 $r$ 递减双指针找到最大的 $k$ 即可），则 $dp_{l,r}$ 会加上 $\sum_{i=r+1}^k\frac{dp_{l,i}}{i-l}$，对每一个 $l$ 维护 $\frac{dp_{l,r}}{r-l}$ 后缀和即可。复杂度 $O(n^2)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5010,mod=1e9+7;
int inv(int a){
	int b=mod-2,r=1;
	while(b){
		if(b&1)r=1ll*r*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return r;
}
void add(int &i,int j){
	i=(i+j>=mod?i+j-mod:i+j);
}
int n;
int s[MAXN],v[MAXN];
int d[MAXN][MAXN],f[MAXN][MAXN],g[MAXN][MAXN],p[MAXN],q[MAXN];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]+=s[i-1];
		v[i]=inv(i);
	}
	d[1][n]=f[1][n]=g[1][n]=v[n-1];
	for(int i=1;i<=n;i++)p[i]=n,q[i]=1;
	for(int h=n-1;h>=1;h--){
		for(int i=1,j=h;j<=n;i++,j++){
			while(s[j]-s[i-1]<=s[p[i]]-s[j])p[i]--;
			add(d[i][j],f[i][j+1]);
			add(d[i][j],mod-f[i][p[i]+1]);
			while(s[j]-s[i-1]<s[i-1]-s[q[i]-1])q[i]++;
			add(d[i][j],g[i-1][j]);
			add(d[i][j],mod-g[q[i]-1][j]);
			if(h>1){
				d[i][j]=1ll*d[i][j]*v[j-i]%mod;
				f[i][j]=f[i][j+1];
				add(f[i][j],d[i][j]);
				g[i][j]=g[i-1][j];
				add(g[i][j],d[i][j]);
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<d[i][i]<<'\n';
	return 0;
}

谢谢观看！