All submissions for this problem are available.
"Nine is considered a good number in Chinese culture because it sounds the same as the word "long-lasting". Hence many
people want their car registration numbers to sum up to 9 on adding the digits recursively.
A car registration number can consist of 1,2,3 or 4 digits. Examples of some good car numbers are 63, 018, 9099, etc. whereas 12,129 are not good.
Why is 9099 good?
9+0+9+9 = 27
2+7 = 9
Similarly it is not difficult to see why 63, 018, 6669, 9999… are good."
Given a string of digits, print how many subsequences of the string result in good car registration numbers.
The zeros at the starting of the number are to be accounted for, i.e. 018 and 18 are different numbers.
First line of the input contains T (T <= 200) denoting the number of test cases. T lines follow each containing a non-empty single
string S. S contains only digits i.e. from [0-9]. Length of S <= 10000.
For each case print how many subsequences of the string result in good car registration numbers. As the answer can be quite large print it modulo 1000000007.
2 10292 0189
|Tags||aug12 dynamic-programming kaushik_iska number-theory|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions