ABC470 F - Googol Swaps

考え方

$10^{100}$ は、好きな回数交換できるという意味と考えてよさそう、という前提でまず考える。

各文字の位置をグラフの頂点と考えて、交換可能なところを辺で結ぶ。
すると、各連結成分内では、十分な回数があれば好きな配置に交換できる。
よって、その個数は、重複のある順列として計算できる。
全連結成分でこれを求めて全てかければ、好きな回数交換できる場合の答えである。

ただし、最後に罠がある。
パリティの問題で、全て異なる文字だった場合、指定配置にできるのは奇数回目か偶数回目のみ。
どの連結成分内も全て異なる文字で構成されている場合、偶数回目に作れるのは積のうち半分だけとなる。

計算量は $O((N+M)\alpha(N))$ である。
ただし、$\alpha(N)$ はアッカーマン関数の逆関数。

入力例1での動作

入力を受け取る。
辺の両端はコード内で 0-indexed に直すので、次のようになる。

n: 5
m: 3
s: "miria"
a, b:
(0, 2)
(1, 4)
(3, 4)

UnionFind木で連結成分を求めると、位置の集合は次の $2$ 個に分かれる。

{0, 2}
{1, 3, 4}

まず、連結成分 {0, 2} を調べる。
この成分にある文字は m, r であり、それぞれ $1$ 個ずつである。
この成分内での並べ方は、$\binom{2}{1}\binom{1}{1}=2$ 通り。
よって、result に $2$ をかける。

result: 2

次に、連結成分 {1, 3, 4} を調べる。
この成分にある文字は i, i, a であり、a が $1$ 個、i が $2$ 個である。
この成分内での並べ方は、$\binom{3}{1}\binom{2}{2}=3$ 通り。
よって、result に $3$ を掛ける。

result: 6

また、同じ連結成分に i が $2$ 個あるので、flag は true になる。
そのため、最後の $2$ で割る処理は行わない。

最後に、result の値である $6$ を出力する。

注意点

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 し、割り算は $998244353-2$ 乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法のアルゴリズムも用意しておくこと。

別解

特になし。