• 显然易得 所有的方案都是一个结果 所以 采取 O（n） 的做法
  用dp[i] 表示第i项的前缀和，t表示 第i项的值
  所以粘第i项时胶水就用了 dp[i-1]*t;

c++代码如下

#include<iostream>
using namespace std;

typedef long long ll;
const int N=1e6;

int n,t,sum=0;

ll dp[N];
ll ans=0;

int main()
{
    dp[0]=0;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>t;
        sum+=t;

        if(i==1) dp[i]=t;
        if(i>1) dp[i]=sum;

        ans+=dp[i-1]*t;
    }

  cout<<ans<<endl;
    return 0;
}