library_checker/graph/
counting_spanning_tree_directed.rs1use competitive::prelude::*;
2use competitive::{algebra::AddMulOperation, math::Matrix, num::mint_basic::MInt998244353 as M};
3
4#[verify::library_checker("counting_spanning_tree_directed")]
5pub fn counting_spanning_tree_directed(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, m, r: usize, edges: [(usize, usize); iter m]);
8 let mut a = Matrix::<AddMulOperation<M>>::zeros((n - 1, n - 1));
9 for (u, v) in edges {
10 if v != r {
11 let v = v - usize::from(v > r);
12 a[v][v] += M::from(1);
13 if u != r {
14 a[u - usize::from(u > r)][v] -= M::from(1);
15 }
16 }
17 }
18 pp!(a.determinant());
19}