この問題において、\(S _ i=S _ j\) かつ \(i\lt j\) なる \((i,j)\) の組があると、その \((i,j)\) を対称な位置になるまで移動させたときの \(2\) 番目の操作を \(1\) 回節約できます。 そのような移動は、文字列の中心を \(\dfrac{i+j}2\) 文字目にするものです。 より厳密には、

• \(N\) が奇数のとき、中央を \(\dfrac{i+j}2\bmod N\) 文字目にするような移動
• \(N\) が偶数のとき、
  • \(i+j\equiv0\bmod 2\) のときはそのような移動は存在しない
  • \(i+j\equiv1\bmod 2\) のときは中央を \(\dfrac{i+j-1}2\) 文字目と \(\dfrac{i+j+1}{2}\) 文字目の間にするような移動および中央を \(\dfrac{i+j-1+N}2\bmod N\) 文字目と \(\dfrac{i+j+1+N}{2}\bmod N\) 文字目の間にするような移動

です。

よって、\(S _ i=S _ j\) かつ \(i\lt j\) なる \((i,j)\) の組に対する \(i+j\) の値にのみ興味があります。 特に、各 \(k\) に対して \(i+j=k\) かつ \(S _ i=S _ j\) かつ \(i\lt j\) なる \((i,j)\) の組の個数 \(C _ k\) がわかるとこの問題が解けることがわかります。

文字 \(c\) に対して、\(T _ c=(T _ {c,i}) _ {1\leq i\leq N}\) を \(T _ {c,i}=\begin{cases}1\quad(S _ i=c)\\0\quad(\text{otherwise})\end{cases}\) で定めます。 すると、\(i+j=k\) かつ \(S _ i=S _ j=c\) なる \((i, j)\) の組の個数は \(T _ c\) の自身との畳み込みによって得られます。 畳み込みによって得る可能性のある値はたかだか \(N\) なので、適切な素数 \(P\) に対する \({}\bmod P\) における値を用いることで畳み込みを \(O(N\log N+\log P)\) で計算することができます。

すべての \(c\) にわたって畳み込みの結果を足した結果 \(T ^ 2\) から、\(i=j\) なる組（これはすべての \(T ^ 2 _ {2i}\) から \(1\) を引くことに対応します）を除いて \(2\) で割ることで求める組の個数 \(C _ k\) が得られます。

これを用いて計算を行うと、全体で計算量は \(O(\sigma(N\log N+\log P))\) 時間となります（\(\sigma=26\) はアルファベットサイズです）。 \(\sigma=26,N=2\times10^5\) でも比較的高速に答えを求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <atcoder/modint>
#include <atcoder/convolution>

int main() {
    using namespace std;
    // constexpr int MOD{469762049}; // N が大きいとき
    constexpr int MOD{65537}; // 2^d | MOD - 1 かつ 2^d >= 2*N が必要 今回は N <= 5000 なので d >= 14 であればよい
    using modint = atcoder::static_modint<MOD>;

    unsigned N;
    unsigned long A, B;
    cin >> N >> A >> B;
    string S;
    cin >> S;

    vector<modint> C(2 * N); // C[k] = (i + j == k かつ S[i] == S[j] かつ i < j なる組 (i, j) の個数)

    const auto char_vector{[&N, &S](const char c) {
        vector<modint> ret;
        ret.reserve(N);
        transform(begin(S), end(S), back_inserter(ret), [&c](const auto i) { return i == c; });
        while (!empty(ret) && ret.back() == 0) ret.pop_back();
        return ret;
    }};
    for (char c{'a'}; c <= 'z'; ++c) {
        // T[i] = (S[i] == c なら 1, そうでなければ 0)
        auto &&T{char_vector(c)};
        // T_sq[k] = (i + j == k かつ S[i] == c かつ S[j] == c なる組 (i, j) の個数)
        auto &&T_sq{atcoder::convolution(T, T)};
        for (unsigned i{}; i < size(T_sq); ++i) C[i] += T_sq[i]; // C[i] = ∑_c T_sq[i]
    }

    for (unsigned i{}; i < N; ++i) --C[2 * i]; // i == j の組を除く
    for (unsigned i{}; i < N; ++i) C[i] += C[i + N]; // index を mod N
    C.resize(N);
    for (auto &&c : C) c *= (MOD + 1) / 2; // i > j の組を除く

    unsigned long ans{numeric_limits<unsigned long>::max()};
    for (unsigned i{}; i < N; ++i)
        // 1 つめの操作を i 回行うと、2 つめの操作は N / 2 - (節約できる個数) 回
        ans = min(ans, A * i + B * (N / 2 - C[(2 * i + N - 1) % N].val()));
    cout << ans << endl;

    return 0;
}