A - Many Formulae Editorial by evima
We should do DP to find the number of ways to form a prefix of the formula so that \(A_i\) follows a
+ or a
More specifically, we should let \(dp[i][j]\) to be the number of ways to arrange a total of \(i\) signs so that no two
-s occur in a row and the last sign is
+ if \(j=0\) and
- if \(j=1\).
For each \(2 \leq i \leq N\), if we fix the sign that comes just before \(A_i\), we can independently decide the first \(i-2\) signs and the last \(N-i\) signs, and we can find the number of ways to set them using the values in \(dp\) above.
The complexity of this solution is \(O(N)\).