Trait BitDpExt

Source

pub trait BitDpExt:
    Sized
    + Copy
    + Default
    + PartialEq
    + Eq
    + PartialOrd
    + Ord
    + Not<Output = Self>
    + BitAnd<Output = Self>
    + BitOr<Output = Self>
    + BitXor<Output = Self>
    + Shl<usize, Output = Self>
    + Shr<usize, Output = Self>
    + Add<Output = Self>
    + Sub<Output = Self>
    + Div<Output = Self>
    + Zero
    + One {
    // Provided methods
    fn contains(self, x: usize) -> bool { ... }
    fn insert(self, x: usize) -> Self { ... }
    fn remove(self, x: usize) -> Self { ... }
    fn is_subset(self, elements: Self) -> bool { ... }
    fn is_superset(self, elements: Self) -> bool { ... }
    fn subsets(self) -> Subsets<Self> ⓘ { ... }
    fn combinations(n: usize, k: usize) -> Combinations<Self> ⓘ { ... }
}

Provided Methods§

Source

fn is_subset(self, elements: Self) -> bool

Examples found in repository ?

crates/competitive/src/algorithm/bitdp.rs (line 37)

36    fn is_superset(self, elements: Self) -> bool {
37        elements.is_subset(self)
38    }

Source

fn is_superset(self, elements: Self) -> bool

Source

fn subsets(self) -> Subsets<Self> ⓘ

Examples found in repository ?

crates/competitive/src/data_structure/submask_range_query.rs (line 86)

82    pub fn get_query(&self, m: u32) -> impl Iterator<Item = (u32, bool)> {
83        let fix = m & self.mask[0];
84        let sub = m & self.mask[1];
85        let sup = (!m) & self.mask[2];
86        sup.subsets().flat_map(move |s| {
87            let inv = s.count_ones() & 1 == 1;
88            sub.subsets().map(move |t| (fix | s | t, inv))
89        })
90    }
91
92    pub fn update_query(&self, m: u32) -> impl Iterator<Item = u32> {
93        let fix = m & self.mask[0] | m & self.mask[1];
94        let sup = (!m) & self.mask[0];
95        let sub = m & self.mask[2];
96        sub.subsets()
97            .flat_map(move |s| sup.subsets().map(move |t| fix | s | t))
98    }

More examples

Hide additional examples

crates/competitive/src/graph/steiner_tree.rs (line 178)

159    pub fn solve<M, I>(&self, terminals: I, weight: M) -> SteinerTreeOutput<'g, S, G, P>
160    where
161        M: Fn(G::Label) -> S::T,
162        I: ExactSizeIterator<Item = G::Vertex>,
163    {
164        let graph = self.graph;
165        let tsize = terminals.len();
166        let states = if tsize == 0 { 0 } else { 1 << tsize };
167        let mut dp: Vec<_> = repeat_with(|| graph.construct_vmap(S::inf))
168            .take(states)
169            .collect();
170        let mut parent: Vec<_> = repeat_with(|| P::init(graph)).take(states).collect();
171        for (i, t) in terminals.enumerate() {
172            *graph.vmap_get_mut(&mut dp[1 << i], t) = S::source();
173        }
174        let inf = S::inf();
175        for bit in 1..states {
176            let (prev, current) = dp.split_at_mut(bit);
177            let dp = &mut current[0];
178            for sub in bit.subsets().skip(1).take_while(|&sub| sub > bit ^ sub) {
179                let left = &prev[sub];
180                let right = &prev[bit ^ sub];
181                for u in graph.vertices() {
182                    let left = graph.vmap_get(left, u);
183                    let right = graph.vmap_get(right, u);
184                    if left != &inf && right != &inf {
185                        let cost = S::mul(left, right);
186                        if S::add_assign(graph.vmap_get_mut(dp, u), &cost) {
187                            P::save_split(graph, &mut parent[bit], u, sub);
188                        }
189                    }
190                }
191            }
192            let mut heap: BinaryHeap<_> = graph
193                .vertices()
194                .filter_map(|u| {
195                    let d = graph.vmap_get(dp, u);
196                    (d != &inf).then(|| PartialIgnoredOrd(Reverse(d.clone()), u))
197                })
198                .collect();
199            while let Some(PartialIgnoredOrd(Reverse(d), u)) = heap.pop() {
200                if graph.vmap_get(dp, u) != &d {
201                    continue;
202                }
203                for neighbor in graph.neighbors(u) {
204                    let v = neighbor.to;
205                    let label = P::label(&neighbor.label);
206                    let nd = S::mul(&d, &weight(neighbor.label));
207                    if S::add_assign(graph.vmap_get_mut(dp, v), &nd) {
208                        P::save_parent(graph, &mut parent[bit], u, v, label);
209                        heap.push(PartialIgnoredOrd(Reverse(nd), v));
210                    }
211                }
212            }
213        }
214        SteinerTreeOutput { graph, dp, parent }
215    }