SUBSHARD - Subset and upset (HARD)
The whole world is crazy about subset sum. We define subset sum as sum of all subparts. A subpart is a number which is obtained by erasing certain digits and arranging the remaining numbers in the same order. You have to calculate the subset sum of the given number. Since the number can be very large return the subset sum modulo m.
For example if the number is 1357, then the various subparts are 1, 3, 5, 7, 13, 15, 17, 35, 37, 57, 137, 135, 157, 357, 1357.
Input
First line contains T (1 ≤ T ≤ 50) denoting the number of test cases.
Next T lines containing two numbers n (0 < n < 101000) and m(1 < m < 109).
Output
Print the subset sum modulo m.
Example
Input: 6 111 9 111 200 456 9 456 1000 1357 1000 1357 5000 Output: 3 147 6 618 333 2333
Time Limit ≈ 2*(My Python 3 Program Top Speed)
hide comments
|
Rishabh Joshi:
2015-05-31 16:03:34
Can you please check my solution. O(n) getting TLE.
|
|
Anmol Garg:
2014-06-30 14:59:03
My 50th. :D |
|
gabber:
2012-12-25 16:42:50
Use MOD only where you need it! |
|
R:
2012-12-11 09:57:38
@author
|
|
♘Prabhat:
2012-10-12 02:10:15
@Tjandra can you please check my code(ID 7834532) why i'm getting this compilation error
|
|
:D:
2012-10-11 21:56:48
Yes :) |
|
Alex Anderson:
2012-10-09 19:20:17
Just confirming, you guys meant O(log n) and O(log^2 n), right? |
|
Problem Solver:
2012-10-08 15:11:56
Yeah, solved this problem, it's very nice, thanks. |
|
Ehor Nechiporenko:
2012-10-04 11:49:46
So nice!!! What about codegolf challenge version of the problem? Last edit: 2012-10-04 11:49:59 |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-04 11:10:46
I think 1 seconds time limit is the best setting ;-)
|
| Added by: | Tjandra Satria Gunawan |
| Date: | 2012-10-03 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Hard version of NITT5 problem. |
RSS