交叉乘

题目大意:求 \[ \sum_{i=l}^r \times \sum_{j=i+1}^ra[i] \times a[j] \]

化简式子:

\[ \begin{aligned} &\sum_{i=l}^r \times \sum_{j=i+1}^ra[i] \times a[j]\\ &=\sum_{i=l}^r a[i] \times (\sum_{j=i+1}^r a[j])\\ &=\sum_{i=l}^r a[i] \times (sum[r] - sum[i])\\ &=sum[r] \times (sum[r] - sum[l - 1]) - \sum_{i=l}^r a[i] \times sum[i]\\ \end{aligned} \]

观察到发现后面那一堆没有同类项了,因此设

\[p[k] = \sum_{i=1}^k a[i] \times sum[i]\]

因此式子化简为:

\[sum[r] \times (sum[r] - sum[l - 1]) - (p[r] - p[l - 1])\]

代码自己可写.

后记:

加深sigema与前缀和应用.