AGC028 B – Removing Blocks 题解【概率期望】

点击量：210

    一道区间统计问题。

目录

Problem Statement

There are \(N\) blocks arranged in a row, numbered \(1\) to \(N\) from left to right. Each block has a weight, and the weight of Block \(i\) is \(A_i\). Snuke will perform the following operation on these blocks \(N\) times:

 

• Choose one block that is still not removed, and remove it. The cost of this operation is the sum of the weights of the blocks that are connected to the block being removed (including itself). Here, two blocks \(x\) and \(y (x\le y)\) ) are connected when, for all \(z(x\le z\le y)\), Block \(z\) is still not removed.

 

There are \(N!\) possible orders in which Snuke removes the blocks. For all of those \(N!\) orders, find the total cost of the \(N\) operations, and calculate the sum of those \(N!\) total costs. As the answer can be extremely large, compute the sum modulo \(10^9+7\).

 

Constraints

• \(1\le N\le 10^5\)
• \(1\le A_i\le 10^9\)
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

N
A1 A2 … AN

Output

For all of the \(N!\) orders, find the total cost of the \(N\) operations, and print the sum of those \(N!\) total costs, modulo \(10^9+7\).

---

Sample Input 1

2
1 2

Sample Output 1

9

First, we will consider the order “Block \(1\) -> Block \(2\)”. In the first operation, the cost of the operation is \(1+2=3\), as Block \(1\) and \(2\) are connected. In the second operation, the cost of the operation is \(2\), as only Block \(2\) remains. Thus, the total cost of the two operations for this order is \(3+2=5\).

 

Then, we will consider the order “Block \(2\) -> Block \(1\)”. In the first operation, the cost of the operation is \(1+2=3\), as Block \(1\) and \(2\) are connected. In the second operation, the cost of the operation is \(1\), as only Block \(1\) remains. Thus, the total cost of the two operations for this order is \(3+1=4\).

 

Therefore, the answer is \(5+4=9\).

 

Sample Input 2

4
1 1 1 1

Sample Output 2

212

Sample Input 3

10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

880971923

题意：

    给定一个长为\(n\)的序列，每个元素有权值\(a_i\)，接下来进行\(n\)次操作，每次在剩下的元素中随机选一个删掉，代价是这个元素所在连通区域的所有元素代价和。问对于所有可能的\(n!\)种操作顺序，所有操作顺序所导致的代价和对\(10^9+7\)取模的值是多少。

题解：

    求所有操作顺序的代价和，实际上就是求这些操作的期望\(\times n!\)。这是一种比较好的转化问题的方式，不过这个题的重点不在转化，而是怎么求答案。

    我们的目的是求出对于一个元素\(i\)，它做了多少贡献，也就是它所在的每一个联通块分别出现了几次。我们用\(P(i,j)\)来表示\(i\)被删掉时\(j\)与\(i\)在一个联通块的概率是多少。

    这个联通块的大小其实无所谓，因为计算答案与联通块大小没有关系。那么当\((i,j)\)“连坐”时，说明\([min(i,j),\max(i,j)]\)区间内的所有元素都没有被删除，那么这里连坐的概率就是\(i\)作为\([\min(i,j),\max(i,j)]\)中第一个被删除的数的概率，这个概率就比较好求了，也就是\(\frac 1{|i-j|+1}\)。

    我们如果求的是期望，那么每个数\(x\)的贡献就是\(a_x\cdot \sum_{i=1}^n P(x,i)\)了。这里我们处理出\([1,n]\)所有数的逆元，然后存到前缀和里。然后利用逆元前缀和算出\(\sum_{i=1}^n P(x,i)=sum[x]+sum[n-x+1]-1\)就可以了。

    因为逆元可以在\(O(n)\)的时间复杂度内求出，因此整个程序的时间复杂度是\(O(n)\)。这里偷懒用了O(nlogn)反正也能过= =，O(n)的做法置顶帖应该有orz

Code：

#include<cstdio>
#include<cstring>
int a[100100];
int sum[100100];
int inv(int x)
{
    long long ans=1,m=x;
    int y=1000000005;
    while(y)
    {
        if(y&1)
            ans=ans*m%1000000007;
        m=m*m%1000000007;
        y>>=1;
    }
    return ans;
}
int main()
{
    int ans=0;
    int n;
    long long fact=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        sum[i]=(sum[i-1]+inv(i))%1000000007;
        fact=fact*i%1000000007;
    }

    for(int i=1;i<=n;++i)
        ans=(ans+(long long)a[i]*(sum[i]+sum[n-i+1]-1)%1000000007)%1000000007;
    printf("%lld\n",fact*ans%1000000007);
    return 0;
}