haar_lib/typical/double_sigma/sum.rs
1//! 2要素の和の総和
2
3use std::{iter::repeat_n, ops::Add};
4
5use crate::num::one_zero::Zero;
6
7/// 2要素の和の総和 $\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N a_i + a_j$
8///
9/// **Time complexity** $O(|a|)$
10pub fn sum_of_sum_of_sum<T>(a: Vec<T>) -> T
11where
12 T: Copy + Add<Output = T> + Zero,
13{
14 let n = a.len();
15 let s = a.into_iter().fold(T::zero(), |x, y| x + y);
16 repeat_n(s, n - 1).fold(T::zero(), |x, y| x + y)
17}