嘘~ 正在从服务器偷取页面 . . .

[AGC028B] Removing Blocks 题解

发布日期: 2024-06-18

更新日期: 2024-06-18

文章字数: 768

[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;
}