haar_lib/math/convolution/
conv_or.rs

1//! $\mathtt{a_{i \lor j}} = \sum \mathtt{f_{i}} * \mathtt{g_{j}}$を満たす`a`を求める。
2use crate::math::convolution::{mobius::*, zeta::*};
3use std::ops::{Add, Mul, Sub};
4
5/// $\mathtt{a_{i \lor j}} = \sum \mathtt{f_{i}} * \mathtt{g_{j}}$を満たす`a`を求める。
6pub fn convolution_or<T>(mut f: Vec<T>, mut g: Vec<T>) -> Vec<T>
7where
8    T: Copy + Add<Output = T> + Sub<Output = T> + Mul<Output = T>,
9{
10    assert!(f.len() == g.len());
11    fast_zeta_subset(&mut f);
12    fast_zeta_subset(&mut g);
13    for (x, y) in f.iter_mut().zip(g.into_iter()) {
14        *x = *x * y;
15    }
16    fast_mobius_subset(&mut f);
17    f
18}