【题解】[AGC028B] Removing Blocks
题意：
给定长度为 $n$ 的序列 $\{a_n\}$，现需将 $n$ 个元素全部删除。删除元素 $i$ 的时候，设包括 $i$ 的极长未被删除区间为 $[l,r]$，则代价为 $\sum_{p=l}^r a_p$。
求 $n!$ 种删除顺序的代价和。
$1\le n\le 10^5, 1\le a_i\le 10^9$。
随机一个排列，代价的期望 $\times n!$ 就是答案。
考虑计算每个元素在某一个固定顺序中，贡献到代价中的次数。建立基于删除时间的小根笛卡尔树，则笛卡尔树上一个节点对答案的贡献是子树内 $a_i$ 之和。
子树贡献转变为每个节点的深度贡献，设 $h_i$ 是 $i$ 号点的深度，令根节点深度为 $1$，则代价为 $\sum_{i=1}^n h_i\times a_i$。
因此现在需要求的就是每一个 $h_i$ 的期望 $E(h_i)$。而计算 $h_i$ 等价于计算有多少个 $x$ 是 $i$ 的祖先。
考虑一个排列，若 $x<i$ 且 $x$ 是 $i$ 的祖先，则 $x,x+1,\cdots i-1$ 都应比 $i$ 后删除，这样的方案数占总方案数的 $\dfrac{(i-x)!}{(i-x+1)!}=\dfrac{1}{i-x+1}$。因为只有这 $i-x+1$ 个元素的相对顺序是重要的，其中恰好有 $\dfrac{1}{i-x+1}$ 个排列满足 $i$ 在最前面被删除。
同理，当 $x>i$，$x$ 是 $i$ 的祖先的概率是 $\dfrac{1}{x-i+1}$。
因此有：
$$ E(h_i)=\sum_{x=1}^{i-1} \dfrac{1}{i-x+1}+\sum_{i+1}^{n}\dfrac{1}{x-i+1}+1 $$
设：
$$ s_x=\sum_{i=1}^x \dfrac{1}{i} $$
则：
$$ E(h_i)=s_{i}+s_{n-i+1}-2+1=s_i+s_{n-i+1}-1 $$
因此答案为：
$$ n!\times \sum_{i=1}^n (s_i+s_{n-i+1}-1)\times a_i $$
时间复杂度 $\mathcal{O}(n)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 1e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, Ans = 0;
int a[MAXN], sum[MAXN], Inv[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n); Inv[1] = 1;
for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 2; i <= n; ++i) Inv[i] = Inv[mod % i] * (mod - mod / i) % mod;
for(int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + Inv[i]) % mod;
for(int i = 1; i <= n; ++i) (Ans += (sum[i] + sum[n - i + 1] - 1) * a[i]) %= mod;
for(int i = 1; i <= n; ++i) Ans = Ans * i % mod;
printf("%lld\n", Ans);
return 0;
}