ADASUM - Ada and Expenses
Ada the Ladybug has just returned from her trips. She noted all her expenses. Sadly, she only had a small piece of paper so she had to keep it in a compressed form. The compressed form is just a very long number. To restore the expenses, simply sum all contigous subsequences of the number. Since this number might be pretty big, you only have to output it modulo 109+7 (1000000007).
Can you help her to restore the number?
The first and the only line of input containts the compressed sequence of digits ([0..9]): 1 ≤ |s| ≤ 2*106
Print the sum of all contigous subsequences
Example Input 2
Example Output 2
Example Input 3
Example Output 3
Example Input 4
Example Output 4
Example Input 5
Example Output 5
Example Input 6
Example Output 6
i figured out solution using following method:
simple 6-8 lines o(n) solution.
Just when I thought I figured out why my Python solution TLE's, still TLE. O(n) with seemingly nothing to optimize further. Any hints, morass?
@Blue.Mary oops i forgot that !, many thanks, got AC
@shubham_001: your solution is not O(n), but O(nlogn), since it executes O(n) time explonent modulo, which has complexity O(logn) per operation.
@morass mine O(n) giving TLE my solution: https://ideone.com/********Last edit: 2017-09-12 11:43:21
@morass thanks :)
@kunal9724kg: Good day to you,
I am constantly getting wa on test case 15 any hint on what might be there in test case 15??
@sultania23: Good day to you,