【题解】[AGC028B] Removing Blocks

· · 题解

题目链接：[AGC028B] Removing Blocks

本题解同步发布于 My Blog

题意：

给定长度为 n 的序列 \{a_n\}，现需将 n 个元素全部删除。删除元素 i 的时候，设包括 i 的极长未被删除区间为 [l,r]，则代价为 \sum_{p=l}^r a_p。

求 n! 种删除顺序的代价和。

随机一个排列，代价的期望 \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;
}