haar_lib/math/convolution/
zeta.rs

1//! 高速Ζ変換
2use std::ops::Add;
3
4/// $\mathtt{F_j} = \sum_{\mathtt{i \supseteq j}} \mathtt{f_i}$を満たす`F`を求める。
5///
6/// `f`の長さは$2^n$であるとする。
7///
8/// **Time complexity** $O(2^n n)$
9pub fn fast_zeta_superset<T>(f: &mut [T])
10where
11    T: Copy + Add<Output = T>,
12{
13    let n = f.len();
14    let t = n.trailing_zeros();
15    assert!(n.is_power_of_two());
16
17    for i in 0..t {
18        let i = 1 << i;
19        for j in 0..n {
20            if j & i == 0 {
21                f[j] = f[j] + f[j ^ i];
22            }
23        }
24    }
25}
26
27/// $\mathtt{F_j} = \sum_{\mathtt{i \subseteq j}} \mathtt{f_i}$を満たす`F`を求める。
28///
29/// `f`の長さは$2^n$であるとする。
30///
31/// **Time complexity** $O(2^n n)$
32pub fn fast_zeta_subset<T>(f: &mut [T])
33where
34    T: Copy + Add<Output = T>,
35{
36    let n = f.len();
37    let t = n.trailing_zeros();
38    assert!(n.is_power_of_two());
39
40    for i in 0..t {
41        let i = 1 << i;
42        for j in 0..n {
43            if j & i != 0 {
44                f[j] = f[j] + f[j ^ i];
45            }
46        }
47    }
48}
haar_lib/math/convolution/zeta.rs

haar_lib/math/convolution/
zeta.rs
