haar_lib/algo/
num_subseq.rs

1//! 相異なる部分列の総数
2
3use std::collections::HashMap;
4use std::hash::Hash;
5
6/// 返り値`ret`に対して、`ret[i]`は`a[0..i]`の相異なる部分列の総数
7///
8/// **Time complexity** $O(|a|)$
9pub fn num_subseq<T: Hash + Eq + Copy>(a: &[T], m: u64) -> Vec<u64> {
10    let n = a.len();
11    let mut dp = vec![0; n + 1];
12    dp[0] = 1;
13
14    let mut tbl = HashMap::new();
15
16    for (i, x) in a.iter().enumerate() {
17        let mut t = dp[i] * 2 % m;
18
19        if let Some(&j) = tbl.get(x) {
20            t = (t + m - dp[j]) % m;
21        }
22
23        dp[i + 1] = t;
24
25        tbl.insert(x, i);
26    }
27
28    dp
29}