It is just (A₁ + 1)(A₂ + 1)...(A_n + 1) - 1. Expand it for proof.

You can solve it by a simple O(n) DP approach.

let's suppose we have the answer to the prefix array ending at i — 1. if we add one element, which is a[i] then the answer for the prefix ending at i is:

ans[i] = ans[i — 1] + ans[i — 1]*a[i] + a[i];

• ans[i — 1] << case where we don't include a[i] in the previous calculated subsequences
• ans[i — 1]*a[i] << case where we include it
• a[i] << case where we take it alone

and finally, the answer is just ans[n] of course

Here's an example code: https://ideone.com/VbqE9b