题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学自幼学习乘法和加法，并且小葱同学意识到，正是因为有了加法和乘法，才能够计算1+1=2和1×1=1这种高深的问题。现在小葱给你N个数a1,a2,⋯,aN，求下列式子的值：
小葱同学自幼学习乘法和加法，并且小葱同学意识到，正是因为有了加法和乘法，才能够计算1+1=2和1×1=1这种高深的问题。现在小葱给你N个数a1,a2,⋯,aN，求下列式子的值：
输入
第一行一个数N。
接下来一行N个数代表a1,a2,⋯,aN。
接下来一行N个数代表a1,a2,⋯,aN。
输出
一行一个数代表答案对1012+7取模之后的结果。
样例输入
5
3 2 1 5 4
样例输出
125
提示
对于40%的数据，N≤50。
对于60%的数据，N≤100。
对于80%的数据，N≤1000。
对于90%的数据，1≤ai≤105。
对于100%的数据，N≤4×104,1≤ai≤1012。
对于60%的数据，N≤100。
对于80%的数据，N≤1000。
对于90%的数据，1≤ai≤105。
对于100%的数据，N≤4×104,1≤ai≤1012。
题解
注意一个条件，i<j&&ai>aj，很明显(ai,aj)是一对逆序对，所以呢，这一题归根到底就是一道与逆序对有关的题。呐，既然与逆序对有关，可以用树状数组（线段树），merger sort来做啦。要先计算出一对逆序对的乘积被累加多少次，这个涅，也好算，就是看(i,j)在多少个(l,r)里出现，很明显(i,j)，在左端点<=i且右端点>=j的区间出现，也就是总共出现了i*(n-j+1)次，也就是ai*aj被累加了i*(n-j+1)次。
如果用树状数组（线段树）做的话需要先离散一下，归并排序的话建议用结构体存一下前缀和(ai*i)。乘法计算嘛，可以提取公因数咯，所以枚举到一个aj，乘前面大于aj的数(ai)的和就可以了。因为ai的数值比较大，还要套一个大整数取模。
#include<map> #include<cstdio> #include<iostream> #define Mod 1000000000007 using namespace std; typedef long long LL; const int N=404000; struct Node { LL x,sum,tmp,i; }g[N],f[N]; int n; LL ans; inline LL mul(LL a,LL b) { LL sum=0; if(a>b)swap(a,b); while(b) { if(b&1ll)sum=(sum+a)%Mod; a=(a*2ll)%Mod;b>>=1; } return sum%Mod; } inline void mgsort(int l,int r) { if(l>=r) return; int mid=l+r>>1; mgsort(l,mid); mgsort(mid+1,r); int i=l,j=mid+1,t=l; while(i<=mid&&j<=r) { if(g[j].x<g[i].x) { ans=(ans+mul(mul((g[mid].tmp-g[i-1].tmp+Mod)%Mod,g[j].x%Mod),n-g[j].i+1))%Mod; f[t++]=g[j++]; } else { f[t++]=g[i++]; } } while(i<=mid) f[t++]=g[i++]; while(j<=r) f[t++]=g[j++]; for(int i=l;i<=r;i++) g[i]=f[i]; for(int i=l;i<=r;i++) g[i].tmp=(g[i-1].tmp+g[i].sum)%Mod; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&g[i].x); g[i].i=1LL*i; g[i].sum=mul(g[i].x,1LL*i)%Mod; g[i].tmp=(g[i-1].tmp+g[i].sum)%Mod; } mgsort(1,n); printf("%lld\n",ans); return 0; }