AGC028 B Removing Blocks

题面

给出一个序列,每个点都有一个权值,一开始他们都是连通的。

Snuke将执行以下操作N次:

  • 选择一个点并将其移除,移除这个点所用的代价为此时他所在的块内所有点的权值和(包括自己),将这个点移除之后原本所在的块会因为其被删除而被分成两个块。

对于所有可能的 $N!$ 个选择方案,算出他们的代价总和。

比如:

Input

2

1 2

Output

9

题解

我在比赛的时候没有写出来这一题,第二天看题解,感觉还是非常神奇的。

我们忽略选择顺序,来算一个选择方案中的所有代价的总和的期望

考虑单点对整体算贡献的方法,我们考虑一个点,其会被包括(也就是有贡献)的期望概率。

假设删除某个点 $i$ 时,点 $j$ 和它在同一个块中的概率为 $P(i,j)$ ,那么如果要满足此时两点在同一个块,就需要选择 $i$ 时:$i,i+1,\cdots ,j$ 都没有被选择过。

那么概率其实就是 $1/(|j-i|+1)$,就是$i$~$j$中只选则到$i$的概率。

我们设$b[j]=\sum_{i=1}^{N} P(i,j)$:

然后一个点 $i$ 的期望贡献就是 $a[i]*b[i]$

最后将所有点的期望值相加 $\times N!$ 就是答案。

可以通过预处理 $1/1,1/2,1/3,\cdots ,1/N$ 的前缀和(模$10^9+7$意义下)做到时间复杂度$O(N)$。

代码

#include <bits/stdc++.h>
#define MAX_N 100007
#define MOD 1000000007
using namespace std;
typedef long long ll;

int N;
ll a[MAX_N], b[MAX_N];
ll inv[MAX_N], sum[MAX_N], res;

inline void init () {
    inv[0] = inv[1] = 1;
    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];
}

int main () {
    scanf("%d", &N);
    for (int i = 1;i <= N; ++i)
        scanf("%d", a + i);
    init();
    for (int i = 1;i <= N; ++i)
        b[i] = (sum[N - i + 1] - 1 + sum[i] + MOD) % MOD;
    for (int i = 1;i <= N; ++i)
        (res += a[i] * b[i]) %= MOD;
    for (int i = 2;i <= N; ++i)
        res = res * i % MOD;
    printf("%lld\n", res % MOD);
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注