DSUBSEQ - Distinct Subsequences
Given a string, count the number of distinct subsequences of it ( including empty subsequence ). For the uninformed, A subsequence of a string is a new string which is formed from the original string by deleting some of the characters without disturbing the relative positions of the remaining characters.
For example, "AGH" is a subsequence of "ABCDEFGH" while "AHG" is not.
First line of input contains an integer T which is equal to the number of test cases. You are required to process all test cases. Each of next T lines contains a string s.
Output consists of T lines. Ith line in the output corresponds to the number of distinct subsequences of ith input string. Since, this number could be very large, you need to output ans%1000000007 where ans is the number of distinct subsequences.
Input: 3 AAA ABCDEFG CODECRAFT Output: 4 128 496
Constraints and Limits
T ≤ 100, length(S) ≤ 100000
All input strings shall contain only uppercase letters.
|Added by:||Ajay Somani|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: C++ 5|
|Resource:||CodeCraft 08, Problem Setter: Jin Bin|
stored strlen(s) in a different variable....and got ac after 10 tles!!!!!!
If getting wrong answers , make sure of following points :
Dynamic programming :) is beautiful!
not so simple as i thought..
was fun solving this problem :)
great question to test knowledge abt modulus
New time limit (set during switch to Cube cluster) is too strict for slower languages. My former Python AC solution (using psyco) cannot pass any more.
getting WA#1 :(
Finally AC...don't use long long.
linear time and still time limit exceeded. Tried switching from python to java and c++, but couldn't get them even past compilation on with these ancient versions of the language. I give up