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
Vikrant Singh:
2016-03-02 10:38:39
beauty ! |
|
PRANJIT BHARALI:
2016-02-04 22:22:33
be careful with MOD ...!!!
|
|
SM_92:
2015-12-25 13:08:34
Thanks to Shashank Tiwari for his comment , got ac after correcting mod problem. |
|
Utkarsh Agarwal:
2015-12-08 02:07:01
Any python code accepted ?? mine is giving tle . same logic accepted in c++ |
|
rahul2907:
2015-09-26 14:05:23
do, if value of sum<0 then sum+=MOD
|
|
7Bubble:
2015-09-01 12:31:43
This may be helpful.
|
|
kartikeya :
2015-07-13 14:56:37
stored strlen(s) in a different variable....and got ac after 10 tles!!!!!!
|
|
Shashank Tiwari:
2015-07-01 11:40:23
If getting wrong answers , make sure of following points :
|
|
xxbloodysantaxx:
2015-07-01 08:52:38
Dynamic programming :) is beautiful! |
|
ISHANI:
2015-02-25 15:07:02
not so simple as i thought.. |
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 |