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要素の和の総和
8///
9/// Σ{i = 1 ~ N - 1}Σ{j = i + 1 ~ N} aᵢ + aⱼ
10///
11/// **Time complexity** $O(|a|)$
12pub fn sum_of_sum_of_sum<T>(a: Vec<T>) -> T
13where
14 T: Copy + Add<Output = T> + Zero,
15{
16 let n = a.len();
17 let s = a.into_iter().fold(T::zero(), |x, y| x + y);
18 repeat_n(s, n - 1).fold(T::zero(), |x, y| x + y)
19}