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
Swapnil Borse:
2014-12-29 14:24:06
was fun solving this problem :) |
|
rajat arora:
2014-12-17 15:56:17
great question to test knowledge abt modulus |
|
numerix:
2014-11-27 07:39:28
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.
|
|
tranquil:
2014-05-23 17:01:45
getting WA#1 :(
|
|
P_Quantum:
2014-05-23 10:36:06
Finally AC...don't use long long. |
|
Nadbor Drozd:
2014-01-22 11:31:06
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 |
|
Savan Popat:
2014-01-08 14:49:35
anybody please explain for which case answer will be negative. |
|
Ankit Jain:
2014-01-02 09:44:27
ok..so after reading the previous comments...googled a bit about modulus...modified the solution...got ac.....but still unable to understand as to which test case gives us a negative value of dp[] because of which all this trouble is occuring...thanks in advance to anybody willing to explain this weird bahviour... |
|
Rishabh Saxena:
2013-12-17 23:58:11
for those getting Wrong Answer #1.....they should look into the fact that they can get negative answer!!
|
|
aqfaridi:
2014-04-08 23:55:38
good problem. think dp .. Last edit: 2013-05-31 11:04:48 |
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 |