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$ 個ずつなので、この連結成分内の並べ方は ${}_{2}\mathrm{C}_{1}\times{}_{1}\mathrm{C}_{1}=2$ 通りである。

位置 $\{1,3,4\}$ にある文字は i, i, a である。
a が $1$ 個、i が $2$ 個なので、この連結成分内の並べ方は ${}_{3}\mathrm{C}_{1}\times{}_{2}\mathrm{C}_{2}=3$ 通りである。

したがって、連結成分ごとの並べ方を独立に選ぶと $2\times3=6$ 通りある。

また、後者の連結成分には同じ文字 i が $2$ 個ある。
同じ文字同士を交換すれば、文字列を変えずに置換の偶奇だけを変えられる。
そのため、この入力では $2$ で割る必要はない。

よって、答えは $6$ となる。

注意点

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

別解

特になし。