Variety of Strings

まず、操作 $2$ のみ行うことを考えます。 操作 $2$ は何度でも行えるので、 $S$ の奇数番目の文字同士、偶数番目の文字同士を自由に並び替えることができます。

ここで、$\\$ $S$ の奇数番目の文字のうち、"a" の個数を $a,$ "b" の個数を $b, ...,$ "z" の個数を $z$ とおくと、奇数番目の文字の並び替えは $\displaystyle \frac{\lceil \frac{N}{2} \rceil}{a! \cdot b! \cdots z!}$ $\\$ $S$ の偶数番目の文字のうち、"a" の個数を $A,$ "b" の個数を $B, ...,$ "z" の個数を $Z$ とおくと、偶数番目の文字の並び替えは $\displaystyle \frac{\lfloor \frac{N}{2} \rfloor}{A! \cdot B! \cdots Z!}$ $\\$ となります。

これらは互いに独立であるため、操作 $1$ を行わないときの $S$ の並び替えは $\displaystyle\frac{\lceil \frac{N}{2} \rceil}{a! \cdot b! \cdots z!} \times \frac{\lfloor \frac{N}{2} \rfloor}{A! \cdot B! \cdots Z!}$ 通りです。

さて、$S_1, S_2$ に操作 $1$ を行うことを考えます。$\\$ $S_1 =$ "a" $, S_2 =$ "b" であるとき、上の式は

$\displaystyle\frac{\lceil \frac{N}{2} \rceil}{(a - 1)! \cdot (b + 1)! \cdots z!} \times \frac{\lfloor \frac{N}{2} \rfloor}{(A + 1)! \cdot (B - 1)! \cdots Z!}$

のようになります。

なお、これは $i, i+1$ の偶奇に則っているため、$\\$ $S_2 =$ "a" $, S_3 =$ "b"のときは

$\displaystyle\frac{\lceil \frac{N}{2} \rceil}{(a + 1)! \cdot (b - 1)! \cdots z!} \times \frac{\lfloor \frac{N}{2} \rfloor}{(A - 1)! \cdot (B + 1)! \cdots Z!}$

となることに注意してください。

これを $1 \leq i \leq N - 1$ において、隣り合うアルファベットの組み合わせについて、重複を除いた後に上の処理を考えると、この問題を解くことができます。