题意简述

对于一个排列 ${p= \{ 1,2,...,n\}}p={1,2,...,n}$，记 $\text{val}(p)$ 等于最小的 $i$ 满足 ${i}> a_ii>a$ ，如不存在则 $\text{val}(p)=n+1$ 。求 $\text{val}(p)$ 的期望值，答案对 $998244353$ 取模。

题解

令 $k=n+1-i$​ ，枚举 $a_i=j$​ ，则前 $i-1$​ 个数的可行的方案为:

$sum_i=$ $\sum \limits_{j=1}^{i-1}(k+1)^{i-1-j} \times k^j$

大力观察发现是等比数列。

等比数列求和公式：

$\sum \limits _{k=0}^{n-1}(x \times a^{k}) = x \times (\frac{a^{n}-1}{a-1})$

所以带入化简得到：

$sum_i= $ $(k+1)^{n-k} \times (\frac{(\frac{k}{k+1})^{n-k}-1}{(\frac{k}{k+1}-1)})\times \frac{k}{k+1}$

​ $= (k+1)^{n-k} \times(1-(\frac{k}{k+1})^{n-k}) \times k$

​ $= k\times((k+1)^{n-k}-k^{n-k}) $

因为枚举 $i$ 和枚举 $k$ 本质上都是一样的。

故答案为:

$ans = \sum \limits_{k=0}^{n-1}sum_k \times i \times (k-1)!$

​ $= \sum \limits_{k=0}^{n-1} (n+1-k) \times k\times((k+1)^{n-k}-k^{n-k}) \times (k-1)!$

​ $= \sum \limits_{k=0}^{n-1} (n+1-k) \times k! \times((k+1)^{n-k}-k^{n-k})$

然后就可以 $\mathcal{O}(n\log{n})$ 搞过去了。

Code

#include <bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;

inline int read() {
    int x=0, w=1;
    char ch=getchar();
    while (ch>'9'||ch<'0') {if(ch=='-') w=-1;ch=getchar();}
    while (ch >='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x * w;
}

const int mod=998244353;
int n,ans;
int jc[N];
int ksm(int x,int k){
    int sum=1;
    while(k){
        if(k&1) sum=sum*x%mod;
        x=x*x%mod;k>>=1;
    }
    return sum;
}
signed main(){
    n=read();
    jc[0]=1;for(int i=1;i<=n;++i) jc[i]=jc[i-1]*i%mod;
    for(int k=0;k<=n;++k){
        ans+=(n-k+1)*jc[k]%mod*(ksm(k+1,n-k)-ksm(k,n-k)+mod)%mod;
        ans%=mod;
    }
    printf("%lld",ans*ksm(jc[n],mod-2)%mod);
    return 0;
}

Add :
还可以OEIS大力观察得出结论