haar_lib/math/convolution/
conv_and_or.rs

1//! 添字AND・OR畳み込み
2use crate::math::convolution::{mobius::*, zeta::*};
3use std::ops::{Add, Mul, Sub};
4
5/// $h_{i \land j} = \sum f_i g_j$を満たす$h$を求める。
6///
7/// # Requirements
8/// `f.len()` = `g.len()`
9pub fn convolution_and<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
10where
11    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
12{
13    assert!(f.len() == g.len());
14    fast_zeta_superset(&mut f);
15    fast_zeta_superset(&mut g);
16    for (x, y) in f.iter_mut().zip(g.into_iter()) {
17        *x = *x * y;
18    }
19    fast_mobius_superset(&mut f);
20    f
21}
22
23/// $h_{i \lor j} = \sum f_i g_j$を満たす$h$を求める。
24///
25/// # Requirements
26/// `f.len()` = `g.len()`
27pub fn convolution_or<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
28where
29    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
30{
31    assert!(f.len() == g.len());
32    fast_zeta_subset(&mut f);
33    fast_zeta_subset(&mut g);
34    for (x, y) in f.iter_mut().zip(g.into_iter()) {
35        *x = *x * y;
36    }
37    fast_mobius_subset(&mut f);
38    f
39}
haar_lib/math/convolution/conv_and_or.rs

haar_lib/math/convolution/
conv_and_or.rs
