[AGC028B] Removing Blocks 题解

题目链接：[AGC028B] Removing Blocks

题意：

有 \(N\) 块砖块排列成一行，从左到右编号为 \(1\) 到 \(N\) 。每一个砖块都有一个重量，砖块 \(i\) 的重量为 \(A_i\)。

Snuke 会对这些 \(N\) 个砖块执行如下操作：

选择一个还没有被移除的砖块，然后移除它。这个操作的代价是与被移除的砖块相邻的砖块（包括它自己）的重量之和。我们定义两块砖 \(x\) 和 \(y ~(x \leq y)\) 是相邻的，当且仅当对于所有 \(z ~(x \leq z \leq y)\) ，砖块 \(z\) 仍然没有被移除。

有 \(N!\) 种移除砖块的可能顺序。你需要对于所有可能的顺序计算出移除完所有 \(N\) 块砖块的代价，并计算这些代价的和。由于答案可能非常大，答案需要对 \(10^9+7\) 取模。

数据范围：

\(1 \le n \le 10^5,~1 \le A_i \le 10^9\) 。

这题它本可以问你期望是什么的，但是它偏要问你期望乘以 \(n!\) ，后面忘了。

考虑一个任意排列，对这个排列建立权值为删除时间的满足小根堆性质的笛卡尔树

则笛卡尔树上每个节点对答案的贡献就是子树内的 \(a_i\) 之和。对应到每个节点就是 \(d_i\times a_i\) ，\(d_i\) 是深度。

问题就转化为每个点 \(i\) 的期望深度 \(\mathrm{E}(d_i)\) ，这等价于有多少个 \(x\) 是 \(i\) 的祖先。

对于某个排列，设 \(x < i\) 且 \(x\) 是 \(i\) 的祖先，那么 \(x,\,x+1,\,\cdots,\,i-1\) 都会比 \(i\) 后删除

我们只需考察 \(i\) 和 \(x\) 的相对顺序，那么这样的方案数占总方案数的 \(\frac{(i-x)!}{(i-x+1)!} = \frac{1}{i-x+1}\) 。

同理，若 \(x>i\) ，\(x\) 是 \(i\) 的祖先的概率为 \(\frac{1}{x - i + 1}\) ，那么 \[ \mathrm{E}(d_i) = \sum_{x=1}^{i-1}\frac{1}{x - i + 1} + \sum_{x=i+1}^n\frac{1}{x-i+1} + 1 \] 记 \(H_x = \sum_{i=1}^x\frac{1}{i}\) ，那么 \[ \mathrm{E}(d_i) = H_i + H_{n-i+1} - 1 \] 答案就是 \[ \mathrm{Ans} = n!\sum_{i=1}^n\left(H_i+H_{n-i+1}-1\right) \cdot a_i \] 时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int res, a[N], sum[N], inv[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; inv[1] = 1;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[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++) res = (res + (sum[i] + sum[n - i + 1] - 1) * a[i]) % mod;
    for(int i = 1; i <= n; i++) res = res * i % mod;
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/3bels28t

---

题外话：

感觉最近看紫题好像没什么难度了一样，但是自己想还是想不太出来。