1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

pub mod inter;
pub mod matrix;
pub mod modint;
pub mod string;
#[allow(unused_imports)]
#[cfg(test)]
mod tests {
    use crate::inter::{power, powm, rt};
    use crate::matrix::matrix_pow;
    use crate::modint::Modint;
    use crate::string::{rotate, rotate_diff};
    #[test]
    fn powtest() {
        let result = power(4, 6);
        assert_eq!(result, 4096);
    }
    #[test]
    fn powmod() {
        let result = powm(123456789, 6574837563712, 234567894);
        assert_eq!(result.fact, 120678297);
        let result = powm(12, 7, 15);
        assert_eq!(result.fact, 3);
        let result = powm(73251, 73251, 998244353);
        assert_eq!(result.fact, 21540034);
    }
    #[test]
    fn rttest() {
        let result = rt(4);
        assert_eq!(result, 2);
        let result = rt(100);
        assert_eq!(result, 10);
        let result = rt(1000);
        assert_eq!(result, 31);
        let result = rt(9999);
        assert_eq!(result, 99);
    }
    #[test]
    fn rotation() {
        assert!(rotate("aaaaa".to_string()));
        assert!(!rotate("abcdeecba".to_string()));
        assert!(rotate("abcdedcba".to_string()));
        assert_eq!(0, rotate_diff("abcdedcba".to_string()));
        assert_eq!(4, rotate_diff("dcbaedcba".to_string()));
    }
    #[test]
    fn power_matrix() {
        let k = matrix_pow(
            vec![vec![1000000000, 1], vec![0, 1]],
            998244353,
            1000000000000,
        )[0][1]
            .fact;
        assert_eq!(k, 919667211);
    }
}