Counting Subsequences
Given a string, count all distinct subsequences (not substrings).As defined previously, a subsequence is a collection of characters from the string (they don't have to be contiguous)
For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba).
Input
The string, on one line. It will consist only of lowercase letters.It will be no longer than 100,000 characters long (this is easier than all substrings!)
Output
The number of distinct subsequences.Note that this number may be ridiculously large, so print it mod 10,007.
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
in this problem don't count empty Subsequences I was getting all WAs because of that just print your answer - 1 . note : even in the example they didn't count the empty Subsequence because here are the Subsequences of "aba" { "" , "a" , "b" , "ab" , "ba" , "aba" , "aa" } I wish if the admins would put a note tn the problem statments it will lower the number of WAs alotnote : even in the example they didn't count the empty Subsequence because here are the Subsequences of "aba"
{
"" , "a" , "b" , "ab" , "ba" , "aba" , "aa"
}
I wish if the admins would put a note tn the problem statments it will lower the number of WAs alot