wao.uchiha's blog

Numer of diffent sequence
By wao.uchiha, 11 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
11 years ago, # |
  Vote: I like it -10 Vote: I do not like it 
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
int main()
{
vector<int>V;
V.push_back(3);
V.push_back(3);
V.push_back(5);
V.push_back(6);
sort(V.begin(),V.end());
int b=1;
while(next_permutation(V.begin(),V.end()))++b;
printf("%d\n",b);
}

B is 1 at first because next_permutation doesn't count sorted order. Hope this help. ;-)

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I mean that sub sequence 1 2 has 4 sub seqence {1},{1,2},{2},{}. Although that, thank you for your comment.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

oh yeah! I found it. @NiVeR: N<=10^5, and element is not important.

here is brute code:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

#define rep(i,n) for(int i=0,_n=(n);i<_n;++i)
using namespace std;

typedef vector<int> VI;
set<VI> f;
VI a;
int n,s[100],dp[100];

int main(){
    cin>>n;
    rep(i,n) cin>>s[i];
    rep(i,1<<n){
        a.clear();
        rep(j,n) if (i&(1<<j)) a.push_back(s[j]);
        f.insert(a);
    }
    cout<<f.size()<<'\n';
    return 0;
}

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.

→ Reply