## 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)\).

posted:

last update: