Contest Duration: - (local time) (120 minutes) Back to Home

## 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: