Hi all, I am currently solving a problem that must find the number of different sub seqence of a array that elements can appear more than one example 3 3 5 6. I think the answer is ((number of 1)+1)*((number of 2)+2)*... like 3 3 5 has (2+1)*(5+1)=6 different sub sequences. But it's wrong: 3 5 3 has 7 different sub sequences. Any one help me,please?
B is 1 at first because next_permutation doesn't count sorted order. Hope this help. ;-)
I mean that sub sequence 1 2 has 4 sub seqence {1},{1,2},{2},{}. Although that, thank you for your comment.
314C - Sereja and Subsequences from Codeforces Round 187 (Div. 1) needs you to do almost the same, except for subsequences must be non-decreasing and you are to output sum of product of all such subsequences. Try reading the editorial (though it did not help me) or accepted codes.
Hope it helps.
oh yeah! I found it. @NiVeR: N<=10^5, and element is not important.
here is brute code:
But i has a O(N) solution: We have a1a2...,an the sub sequence that have a[i] is f[i] if a[i] appear before f[i]=sum(f[j],j=1..i-1) if a[i] is first appear f[i]=sum(f[j],j=1..i-1)+1 The result is sum(f[j],j=1..n)+1. P/s: sorry, it's wrong.