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.
Input
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
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.
Example
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.
hide comments
hitachi:
2013-05-15 02:43:16
for those getting WA#1...problem is i think in the mod operation Last edit: 2013-05-15 02:45:16 |
|
:-):
2013-04-24 15:36:17
awesome problem |
|
codecracker:
2013-04-01 23:18:55
mod(x)=x%m working fine...no need for increasing overhead |
|
_maverick:
2013-03-23 16:08:57
wow DP problems fill ma life a gud classic one...
|
|
Kartik Singal:
2012-08-17 23:24:36
nice problem |
|
npsabari:
2012-07-11 18:17:59
Classic! |
|
Symon Rahman:
2012-05-17 21:15:38
Can anyone tell me what is the meaning of WA#1
|
|
Symon Rahman:
2012-05-17 21:03:58
What is the test case 1, I got wa so many times, but my code is right |
|
Praneeth.N:
2012-05-16 08:33:44
I am getting correct answer for the test cases mentioned in the question.But I am getting wrong answer #0.Somebody please kindly explain..Thanks in advance |
|
Giorgos Christoglou:
2012-05-15 17:16:28
wrong answer at testcase 0 . |
Added by: | Ajay Somani |
Date: | 2008-02-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |
Resource: | CodeCraft 08, Problem Setter: Jin Bin |