crates/math/enumerate_inv_mods/src/lib.rs

View this file on GitHub
Last update: 2024-10-18 21:07:52+09:00

Depends on

crates/internals/internal_modint/src/lib.rs

Required by

crates/fps/fps_utils/src/lib.rs

Code

use internal_modint::ModInt;

/// n以下のmod逆元列挙を`O(n)`で行う  
/// index 0には便宜的に0を入れたn+1の長さの配列を返す
pub fn enumerate_invs<M: ModInt>(n: usize) -> Vec<M> {
    let n = n + 1;
    assert!(n <= M::modulus() as usize);
    let mut invs = vec![M::raw(0); n];
    if n <= 1 {
        return invs;
    }
    invs[1] = M::raw(1);
    for i in 2..n {
        invs[i] = -invs[M::modulus() as usize % i] * M::raw(M::modulus() / i as u32);
    }
    invs
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test() {
        use static_modint::ModInt998244353 as MInt;
        const SIZE: usize = 1_000_000;
        let invs = enumerate_invs::<MInt>(SIZE);
        for i in 1..=SIZE {
            assert_eq!(invs[i] * MInt::new(i), MInt::new(1));
        }
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError