Yes, the last problem of last ARC was exceptionally hard but usually ARC tends to be easy. Anyway, you can predict the difficulties from point values.

It may also be solved in O(n²). Let dp[n][l] = number of ways to get length l after n keystrokes. Now answer is dp[n][l] / 2^l with l = s.size() since all strings of same length are equviprobable

It's seems that it's a solution from editorial (I've found 2^m and O(n^2) in it) but I'm not sure.

And now we can add FFT and get solution.

Anyway, the intended O(n²) solution much more beatiful.

I "solved" it in different way. First observe that the answer depends only on N and L = |S|. Then write O(N³) brute-force and display results for N, L ≤ 10. Look at these values and observe that:

f[i][i] = 1

f[i][j] = f[i - 1][j - 1] + 2 * f[i - 1][j + 1].

f[i][j] = f[i][j - 1] if i = j(mod2).

Precompute f[1][N] for N = 1, 2, ..., 5000 with brute-force and include those values in your code (I searched for the sequence in OEIS but failed). Then just use observed formulas to fill the f[][] table.