Hackerrank World CodeSprint 7
Summing Pieces
传送门

题目大意：给你一个数列 把这个数列分成若干个子串 求出所有分法的权值和（权值和的计算方式为：Σ每个子串的长度*每个子串的权值和）（n<=10^6）

首先想到了一个n^2的dp
但是后来不会优化…
于是就想到了贡献法

下面是做法：
一个长度为i的数列的分法为2 ^ (i-1)种
对于位于p的位置的数，假设他左边有L个数，右边有R个数，包含它的子串的长度为n - L - R，
那么他的对答案的贡献为

但是计算一次显然是O（n^2）的 我们需要把它优化到O（1）
我们把这个式子化简一下：

我们假设g(i) = 2 ^ (i-1)
那么我们只要预处理g(i) 和 g(i) * i的前缀和 就可以做到O（1）的转移了

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
const long long mod=1000000007;
const int N=1000010;
long long ans;
int n;
long long sum1[N],a[N],sum2[N],g[N],gi[N];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    g[0]=1;sum1[0]=1;g[1]=1;sum1[1]=1;gi[1]=1;
    for (int i=2;i<=n;i++)
    {
        g[i]=g[i-1]*2%mod;
        gi[i]=g[i]*i%mod;
    }
    for (int i=1;i<=n;i++)
    {
        sum1[i]=(sum1[i-1]+g[i])%mod;
        sum2[i]=(sum2[i-1]+gi[i])%mod;
    }
// for (int i=0;i<=n;i++) cout<<sum1[i]<<" "<<sum2[i]<<endl;
    for (int i=1;i<=n;i++)
    {
        long long sum=0;
        sum=(sum+((sum1[i-1]*sum1[n-i])%mod*n)%mod)%mod;
        sum=(sum+mod-(sum2[i-1]*sum1[n-i])%mod)%mod;
        sum=(sum+mod-(sum2[n-i]*sum1[i-1])%mod)%mod;
        ans=(ans+(sum*a[i])%mod)%mod;
    // cout<<ans<<endl;
    }
    printf("%d\n",ans);
}