Frieren Beyond Journey’s End Solution

考虑对a前缀和得s
$$
\sum_{i=1}^{n}\sum_{l=1}^{i}\sum_{r=i}^{n}\sum_{k=l}^{r}a_k
$$

$$
= \sum_{i=1}^{n}\sum_{l=1}^{i}\sum_{r=i}^{n}(s[r] - s[l - 1])
$$

$$
= \sum_{i=1}^{n}(\sum_{l=1}^{i}\sum_{r=i}^ns[r] - \sum_{l=1}^{i}\sum_{r=i}^ns[l - 1])
$$

$$
= \sum_{i=1}^{n}(\sum_{l=1}^{i}\sum_{r=i}^ns[r] - \sum_{r=i}^{n}\sum_{l=1}^is[l - 1])
$$

$$
= \sum_{i=1}^{n}(i * \sum_{r=i}^ns[r] - (n - i + 1) * \sum_{l=1}^is[l - 1])
$$

可以看出这两公式又可以前缀和即对s前缀和得ss
$$
\sum_{r=i}^n s[r] = ss[n] - ss[i - 1]
$$

$$
\sum_{l=1}^i s[l - 1] = \sum_{l=0}^{i - 1}s[l] = ss[i - 1]
$$

带入进去

$$
= \sum_{i=1}^{n}(i * (ss[n] - ss[i - 1]) - (n - i + 1) * ss[i - 1])
$$

这个是公式变量只有 $i$， $O(N)$ 累加即可

#include<bits/stdc++.h>
using namespace std;

const long long p = 1000000007;

int main(){
	int T = 1;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<int> val(n + 1);
		vector<long long> s(n + 1), ss(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> val[i];
			s[i] = (s[i - 1] + val[i]) % p;
			ss[i] = (ss[i - 1] + s[i]) % p;
		}
		long long res = 0;
		for (long long i = 1; i <= n; i++) {
			res += (ss[n] - ss[i - 1]) * i - ss[i - 1] * (n - i + 1);
			res %= p;
		}
		cout << (res % p + p) % p << endl;
	}
    return 0;
}