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
kabramanan:
2017-05-31 16:30:49
Just add mod wherever you think the answer could be negative.
|
|
kush_code:
2017-05-17 18:20:38
input contains lowercase characters also.
|
|
sfialok98:
2017-04-03 21:33:39
Very nice Problem.....
|
|
nilabja16180:
2017-03-24 15:50:27
GOOD problem! |
|
vunnamtej:
2017-03-09 14:51:24
good dp. string to maths |
|
ipg_2015054:
2017-02-21 19:27:27
@Avik Sarkar how can the value be negative..please explain |
|
prasoonbatham:
2017-01-14 15:17:38
Always check output before submitting. Cost me 1 wa. :(
|
|
kira28:
2017-01-07 19:53:04
FINALLY AC :)
|
|
madhavgaba:
2016-12-30 12:31:23
@VINAYAK if ur answer is negative.....just add MOD to ur answer |
|
vinayak_1997:
2016-12-29 14:05:45
Why will modulo here give negative answer? Last edit: 2016-12-29 14:31:38 |
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 |