i just observed that a number is useful only on the first time it appears. e.g. [2,1,5,2] can be compressed to [{2,1},{1,2},{5,3}]. reduces nk^2 to k^3. then a later number that is smaller is surely worse so reduce it to [{2,1},{5,3}]. "sub k^3" solution passes. the second number is the index

wow instant tutorial!

It will overflow and get junk values

You can check that the array must be in the form 1...3 where "..." represent one or more 2s.

Number of subsequences would for that form would be 2^n — 1, as any number of 2s (except 0) work. But checking all 1s and 3s (say using a prefix count array) would be O(N^2).

O(N) solution would be to count number of 1s so far, i.e. cnt1++. when you encounter 2, double curr and add cnt1. This works similar to the 2^n analysis count above. When encounter 3, you close the subsequence by adding curr to ans.

Remember to mod for each operation

hey you are the iq guy

grrrrr

Auto comment: topic has been updated by Hushpuppy (previous revision, new revision, compare).

me too