自动搬运

查看原文

来自洛谷，原作者为

	dengyaotriangle 我弱弱 您强强 嘤嘤嘤

搬运于2025-08-24 22:16:51，当前版本为作者最后更新于2020-12-03 11:30:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

显然，这题可以线性！

考虑一个点存活时间的期望 $\mathbf E[t_i]$，我们根据一个众所周知的公式有

$$\mathbf E[t_i]=\sum_{x\geq 1}\mathbf P[t_i\geq x]$$

而我们看 $\mathbf P[t_i\geq x]$，这相当于操作 $x$ 轮，没有把 $i$ 和一个比它大的数合并的概率。

显然，我们只需要考虑 $i$ 左右两边第一个比它大的数，这个可以用单调栈 $O(n)$ 求出，我们设它们距离 $i$ 分别是 $a,b$

那么，我们操作 $x$ 轮，一共有 $x!\binom{n-1}{x}$ 种方案，原因就是考虑把合并操作看成两部分，对于排列的 $n-1$ 个空隙，枚举它们有没有被合并在一起，就是 $\binom{n-1}{x}$ 种，然后这 $x$ 种顺序任意，就是 $x!$

考虑其中合法（即没有把 $i$ 合并掉）的方案有几种，我们可以把这 $n-1$ 个空隙分成 3 部分：位于它与它的左边的第一个比它大之间的，共 $a$ 个，位于它与它右边第一个比它大之间的，共 $b$ 个，其它的，$n-1-a-b$ 个。

我们发现，$a,b$ 两部分如果取完了，那么就代表着 $i$ 与比它大的合并了。而若没全取完，则 $i$ 肯定还活着。

所以合法的方案数是

$$x!\sum_{i+j+k=x,i\neq a,j\neq b}\binom{a}{i}\binom{b}{j}\binom{n-1-a-b}{k} $$

当然，由于这题数据范围小，直接用这个式子甚至都能过，我们继续化简

上式显然等于

$$x^a-t^a)((1+t)^b-t^b)(1+t)^{n-1-a-b}$$

拆开之后，易得，

$$x!\left(\binom{n-1}{x}-\binom{n-1-a}{x-a}-\binom{n-1-b}{x-b}+\binom{n-1-a-b}{x-a-b}\right) $$

（或者你用容斥原理也可以推出来上式，但是生成函数多方便）

那么 $\mathbf P[t_i\geq x]$ 就是

$$\frac{x!\left(\binom{n-1}{x}-\binom{n-1-a}{x-a}-\binom{n-1-b}{x-b}+\binom{n-1-a-b}{x-a-b}\right)}{x!\binom{n-1}{x}} $$

至此，这个问题可以 $O(n^2)$，但是我们还需要继续。

因为 $\mathbf E[t_i]=\sum_{x\geq 1}\mathbf P[t_i\geq x]$，所以我们求和

$$\mathbf E[t_i]=\sum_{x\geq 1}\frac{\binom{n-1}{x}-\binom{n-1-a}{x-a}-\binom{n-1-b}{x-b}+\binom{n-1-a-b}{x-a-b}}{\binom{n-1}{x}} $$

我们发现这个和式是由4项形如

$$\sum_{x=1}^{n-1}\frac{\binom{n-1-i}{x-i}}{\binom{n-1}{x}} $$

的东西组成的，而我们化简这个东西

$$\begin{aligned} &\sum_{x=1}^{n-1}\frac{\binom{n-1-i}{x-i}}{\binom{n-1}{x}}\\ =&\sum_{x=1}^{n-1}\frac{(n-1-i)!x!}{(x-i)!(n-1)!}\\ =&\frac1{(n-1)^{\underline{i}}} \sum_{x=1}^{n-1}x^{\underline{i}}\\ =&\frac1{(n-1)^{\underline{i}}} \frac{n^{\underline{i+1}}}{i+1}\\ =&\frac{n}{i+1}\\ \end{aligned} $$

注意上面的东西在 $i=0$ 的时候不成立（因为那个和式化不开），若 $i=0$ 上式显然每一项等于 $1$，就是 $n-1$，而不是 $n$

显然，我们可以线性预处理逆元求出这个式子，那么 $\mathbf E[t_i]$ 也可以 $O(1)$ 求了。

所以总时间复杂度 $O(n)$，注意若左右两边第一个比它大的数不存在需要稍微修改一下式子，也是类似的，就不推了。

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

const int maxn=55;
const int mdn=998244353;

int n;
int a[maxn];
int prv[maxn],nxt[maxn];
int inv[maxn];
int ans[maxn];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    inv[1]=1;for(int i=2;i<=n;i++)inv[i]=inv[mdn%i]*(long long)(mdn-mdn/i)%mdn;
    for(int i=0;i<n;i++)ans[i]=n*(long long)inv[i+1]%mdn;
    for(int i=1;i<=n;i++)cin>>a[i];
    stack<pair<int,int>> stk1,stk2;
    for(int i=1;i<=n;i++)nxt[i]=n+1,prv[i]=0;
    for(int i=1;i<=n;i++){
        while(!stk1.empty()&&stk1.top().first<a[i]){nxt[stk1.top().second]=i;stk1.pop();}
        stk1.push(make_pair(a[i],i));
    }
    for(int i=n;i>=1;i--){
        while(!stk2.empty()&&stk2.top().first<a[i]){prv[stk2.top().second]=i;stk2.pop();}
        stk2.push(make_pair(a[i],i));
    }
    for(int i=1;i<=n;i++){
        vector<int> dis;
        if(prv[i]!=0)dis.push_back(i-prv[i]);
        if(nxt[i]!=n+1)dis.push_back(nxt[i]-i);
        if(dis.empty())cout<<n-1<<' ';
        else if(dis.size()==1){
            int a=dis[0];
            int w=(n-1ll-ans[a]+mdn)%mdn;
            cout<<w<<' ';
        }else{
            int a=dis[0],b=dis[1];
            int w=(n-1ll+mdn*2-ans[a]-ans[b]+ans[a+b])%mdn;
            cout<<w<<' ';
        }
    }
    return 0;
}