Googol Swaps の解説

連結成分Ciでの構成できる個数はこの中の連結成分のアルファベットの個数をそれぞれalpha[i]とすると

ざっくり |Ci| / A[i]! * B[i]! * .... * Z[i]!

と計算できる。 ただし、連結成分の中で偶奇を入れ替えることができなければ偶or奇のどちらかの構成しか取れないので /2する必要がありそう。

偶奇を入れ替えることができるのは同じ連結成分の中に同じものがあること(alpha[i] >= 2を満たすものがあること)なのでこれらを求めれば答え。

fn main() {
    input! {
        n: usize, m: usize,
        s: Chars,
        ab: [(Usize1, Usize1); m]
    }
    let mut uf = Dsu::new(n);
    for &(a, b) in ab.iter() {
        uf.merge(a, b);
    }
    let mut frac = vec![ModInt998244353::new(1)];
    for num in 1..=n {
        frac.push(*frac.last().unwrap() * num);
    }
    
    let g = uf.groups();
    let mut flg = false;
    let mut ans = ModInt998244353::new(1);
    for row in g.iter() {
        let mut map = HashMap::new();
        for &idx in row.iter() {
            map.entry(s[idx]).and_modify(|e| *e += 1).or_insert(1usize);
        }
        if row.len() != map.len() {
            flg = true;
        }
        let v = map.values().collect_vec();
        let mut tt = frac[row.len()];
        for &&num in v.iter() {
            tt /= frac[num];
        }
        ans *= tt;
    }
    if !flg {
        ans /= 2;
    }
    println!("{}", ans);
}