解説

記号をグラフの頂点、置換を有向辺として考えると、 $N$ 頂点 $N$ 辺のグラフになります。

すると、単換字式暗号の適用は、辺に沿って次の頂点へ移動することと考えられます。

これを繰返して元に戻るには、どのサイクルについても適用回数がサイクル長の倍数であることが必要です。

ただし、 $S$ に含まれない文字のみで構成されたサイクルについては無視します。

これによって、サイクル長の最小公倍数を求めることで答えが求まります。

実装方法

次の $2$ つの処理を行う必要があります。

1. サイクルを検出する
2. 最小公倍数を求める

1. サイクルを検出する

このグラフでは連結成分の大きさとサイクル長が等しくなるため、 UnionFind 木を使えば $O(N \alpha(N))$ で各サイクルの長さを検出できます。

2. 最小公倍数を求める

それぞれのサイクル長を素因数分解して頑張ると最小公倍数 $\mod 10^9 + 7$ を求めることができます。

素因数分解せず $\mod 10^9 + 7$ をとりながら求める方法では、正しい答えを求めることが出来ません。

多倍長整数が使える言語では、素因数分解せずに最後に $1$ 回だけ $\mod 10^9 + 7$ を取ると簡単です。

想定 TLE 解法

元に戻るまで適用しつづける $O(M \text{LCM}(C_k) )$ ($C_k$: サイクル長)

サイクル長の最小公倍数の最大値は $N$ が大きくなるに従って指数関数的に大きくなるため、最大ケースでは TLE します。