题解 P6046 【纯粹容器】

· · 题解

显然，这题可以线性！

考虑一个点存活时间的期望 \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![t^x]((1+t)^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;
}