はじめに用語を定義します。
文字列 \(T\) を \(n\) 回繰り返してできる文字列を \(T\) の 累乗 と呼び \(T^n\) と表します。
また、文字列 \(T\) が 原始的 であるとは、\(T\) がある文字列 \(u\) および \(2\) 以上の整数 \(n\) を用いて \(T = u^n\) と表すことができない文字列であることを言います。このとき、文字列 \(S\) に対して正の整数 \(n\) を用いて \(S = T^n\) と表せる原始的な文字列 \(T\) は一意に定まることが確認できます。これを文字列 \(S\) の 原始根 と呼びます。

さて、まずは「\(A + \mathrm{rev}(B)\) と \(\mathrm{rev}(A) + B\) がともに回文である非空な文字列 \(A, B\) 」がどのような性質を持つかを考えます。
\(|A| \leq |B|\) と仮定します。\(\mathrm{rev}(B)\) の suffix は \(A\) と一致するので \(\mathrm{rev}(B) = C + \mathrm{rev}(A)\) とすると

• \(A + C + \mathrm{rev}(A)\) は回文 \(\to\) \(C\) は回文
• \(\mathrm{rev}(A) + B = \mathrm{rev}(B) + A = C + \mathrm{rev}(A) + A\) は回文

であるため、\(C = x, \mathrm{rev}(A) + A = y\) とおくと「\(x, y, x + y\) 全て回文」という関係が成り立ちます。

ここで \(x, y, x + y\) が全て回文であるとき、原始的な文字列 \(T\) と非負整数 \(n, m\) を用いて \(x = T^n, y = T^m, x + y = T^{n+m}\) と表せることが確認できます。

• (証明) \(|x| \leq |y|\) として一般性を失わない。\(x\) は \(y\) の prefix になるため \(y=x+z\) とすると、 \(x+z+x\) は回文なので \(z\) もまた回文となり、「\(z, x, z + x\) が全て回文」という関係が成り立つ。このような操作を再帰的に繰り返すと、ある回文 \(U\) であって \(x\) と \(y\) が \(U\) の累乗となるものが存在することが確認できる。\(U\) の原始根を \(T\) とすると、\(x, y, x + y\) もまた \(T\) の累乗となる。(証明終わり)

よって、\(m\) の偶奇で場合分けすると、次のようになります。

• \(m\) が偶数の時：\(A = T^{m/2}, B = T^{n + m/2}\)
• \(m\) が奇数の時：\(T = \mathrm{rev}(X) + X\) として \(A = X + T^{\lfloor m/2 \rfloor}, B = X + T^{\lfloor m/2 \rfloor + n}\)

\(|A| \geq |B|\) の場合も同様の結論が得られるので、\(A, B\) の条件は全体で次のようになります。

• \(T\) を \(\mathrm{rev}(A) + B\) の原始根とする。(\(T\) は回文になる。) 条件を満たすのは次の 2 通りである。
  
  1. ある正整数 \(n,m\) が存在して、 \(A = T^n, B = T^m\) が成り立つ。
  2. \(T = \mathrm{rev}(X) + X\) を満たす \(X\) およびある非負整数 \(n,m\) が存在して、\(A = X + T^n, B = X + T^m\) が成り立つ。

ここで 2. の場合において \(X \neq \mathrm{rev}(X)\) であるのに注意します。(\(X = \mathrm{rev}(X)\) だと \(T\) が原始的である事実に反する)

次に、良い文字列 \(S\) が与えられた時に条件を満たすように \(A, B\) に分割する箇所が何個あるかを考えます。
\(S\) が回文である場合は \(1.\) のケースに限られることが確認できます。よって \(S = T^n\) としたときに分割する箇所が \(n - 1\) 箇所あります。
\(S\) が回文でない場合は 2. のケースに限られます。
実は、良い文字列 \(S\) が回文でない場合、\(A, B\) に分割する方法は 1 通りしか存在しないことが証明できます。

(証明)
\((A, B), (C, D)\) がともに条件を満たすような分割だとします。今、\(A + \mathrm{rev}(B) = C + \mathrm{rev}(D)\) が成立したとします。このとき \((A, B) = (C, D)\) が成り立つことが証明できます。

• (証明) \(A + \mathrm{rev}(B) = C + \mathrm{rev}(D) = S'\) とする。\(S'\) の原始根 \(T\) を求めて \(T\) から \(X\) を復元することができる。\(X\) が定まると \(S\) を \(S'\) に変換する方法が一意に定まることが確認できる。よって \((A, B) = (C, D)\) が成り立つ。(証明終わり)

よって、任意の分割 \((A, B), (C, D)\) に対して \(A + \mathrm{rev}(B) = C + \mathrm{rev}(D)\) (あるいは \(\mathrm{rev}(A) + B = \mathrm{rev}(C) + D\)) が成り立つことを示せば、分割が一意であることを証明できます。

\(|A| \geq |B|\) であるとき、\(A + \mathrm{rev}(B)\) は回文なので \(S\) の前半を折り返した形になります。\(|C| \geq |D|\) の場合の \(C + \mathrm{rev}(D)\) も同様です。よって \(|A| \geq |B|, |C| \geq |D|\) が成り立つ時は \(A + \mathrm{rev}(B) = C + \mathrm{rev}(D)\) が成立します。
\(|A| \leq |B|, |C| \leq |D|\) の場合も同様の方法で \(\mathrm{rev}(A) + B = \mathrm{rev}(C) + D\) が確認できます。

以降では \(|A| \lt |B|, |C| \gt |D|\) を仮定します。(\(|A| \gt |B|, |C| \lt |D|\) の場合も同様です。)
\((A, B)\) に対応する \(S\) の \(X\) を用いた分解が

\[S = X + \mathrm{rev}(X) + X + \dots + X + X + \dots + X + \mathrm{rev}(X) + X\]

で、同様に \((C, D)\) に対応する \(S\) の \(Y\) を用いた分解が

\[S = Y + \mathrm{rev}(Y) + Y + \dots + Y + Y + \dots + Y + \mathrm{rev}(Y) + Y\]

であるとします。ここで \(X + X\) の \(+\) の部分が \(A\) と \(B\) の切れ目に、\(Y + Y\) の \(+\) の部分が \(C\) と \(D\) の切れ目に対応しています。(\(X \neq \mathrm{rev}(X), Y \neq \mathrm{rev}(Y)\) に注意する。)

\(|A| \lt |B|\) より \(X + X\) の切れ目の部分は全体の半分より左にあります。また、\(X\), \(\mathrm{rev}(X)\) のかたまりは \(S\) 全体で偶数個あるので \(S\) の中心をまたぎません。よって \(X + X\) は \(S\) の左半分に入ります。
同様の議論により、\(Y + Y\) は \(S\) の右半分に入ります。

次に、\(|S| / 2|X|, |S| / 2|Y|\) の偶奇を考えます。
今、\(|S| / 2|Y|\) が偶数とします。\(S\) の左半分は \(Y + \mathrm{rev}(Y) + \dots + Y + \mathrm{rev}(Y)\) となり回文です。一方 \(S\) の左半分には \(X + X\) が含まれているので、\(S\) の左半分は

• \(X + \mathrm{rev}(X) + \dots + X + X + \dots + \mathrm{rev}(X) + X\)
• \(X + \mathrm{rev}(X) + \dots + X + X + \dots + X + \mathrm{rev}(X)\)

のいずれかとなります。これが回文であることを考えると、1 番目の場合は両端を見ると \(X = \mathrm{rev}(X)\) となり矛盾することがわかります。また、\(2\) 番目の場合も両端から見ていくとどこかで \(X = \mathrm{rev}(X)\) となるか、または \(X\) が回文になる必要があり \(X \neq \mathrm{rev}(X)\) に矛盾します。以上より \(|S| / 2|Y|\) が偶数の場合は矛盾が発生します。

同様の方法で \(|S| / 2|X|\) が偶数の場合も矛盾が発生します。よって \(|S| / 2|X|, |S| / 2|Y|\) がともに奇数のケースが残ります。
このとき、\(S\) の中央の切れ目を \(\vert\) で表すとすると、\(|S| / 2|X|, |S| / 2|Y|\) が奇数になることから

\[S = X + \dots + \mathrm{rev}(X) \vert X + \dots + X\]

\[S = Y + \dots + Y \vert \mathrm{rev}(Y) + \dots + Y\]

が成り立ちます。

\(|X| \leq |Y|\) の場合を考えます。\(S\) の中央左側と末尾に注目すると

\[\mathrm{rev}(X) = (Y の \text{suffix}) = X\]

となり矛盾が発生します。\(|X| \geq |Y|\) の場合も \(S\) の中央右側と先頭に注目すると

\[\mathrm{rev}(Y) = (X の \text{prefix}) = Y\]

となり矛盾が発生します。

以上より \(|A| \lt |B|, |C| \gt |D|\) の場合は矛盾が発生することが確認できました。
よって、任意の分割 \((A, B), (C, D)\) に対して \(A + \mathrm{rev}(B) = C + \mathrm{rev}(D)\) あるいは \(\mathrm{rev}(A) + B = \mathrm{rev}(C) + D\) が成り立つことが証明出来て、ここから分割の箇所が一意であることを証明出来ました。(証明終わり)

以上の議論を踏まえた上で包除原理を用いることで、回文の場合と回文でない場合でともに分割の個数を数える問題に帰着して答えを数えることが出来るようになります。(この部分もいくらか複雑ですが詳細は略します) 計算量は \(\mathrm{O}(N \times (N の約数の個数))\) や \(\mathrm{O}(N \log N \times (N の約数の個数))\) 程度で十分高速です。