HackerRank Algebra – Manasa and Sub-sequences

Challenge: Manasa and Sub-sequences

Subdomeniu: Algebra (algebra)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464751486

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/manasa-and-sub-sequences/problem

Cerinta

Manasa recently lost a bet to Amit. To settle the problem, they are playing a game:  

They have _N_ balls in front of them. Each ball, except the 1st ball, is numbered from 0 to 9. The 1st ball is numbered from 1 to 9. 

Amit calculates all the [subsequences](https://en.wikipedia.org/wiki/Subsequence) of the number thus formed. Each subsequence of sequence _S_ is represented by _S<sub>k</sub>_. 

e.g. _S_ = 1 2 3  

_S<sub>0</sub>_ = 1 2 3 ,  
_S<sub>1</sub>_ = 1 2 ,  
_S<sub>2</sub>_ = 1 3 ,  
_S<sub>3</sub>_ = 2 3 ,  
_S<sub>4</sub>_ = 1 ,  
_S<sub>5</sub>_ = 2 , and  
_S<sub>6</sub>_ = 3 .  

Each subsequence _S<sub>k</sub>_ also represents a number. e.g. _S<sub>1</sub>_ represents tweleve, _S<sub>2</sub>_ represents thirteen.

Now Manasa has to throw _S<sub>k</sub>_ candies into an intially empty box, where _k_ goes from 0 to ( maximum number of subsequences -  1).

At the end of the game, Manasa has to find out the total number of candies, _T_, in the box. As _T_ can be large, Amit asks Manasa to tell _T % (10<sup>9</sup> + 7 )_. If Manasa answers correctly, she can keep all the candies. Manasa can't take all this Math and asks for your help.  

Help her!

*Note:* A subsequence can also be have preceding zeros. For example, the sequence _103_ has subsequences _103_, _10_, _13_, _03_, _1_, _0_, and _3_ (so both _03_ and _3_ are counted separately).

**Input Format**  
A single line containing a number having _N_ digits.  


**Output Format**  
A number contaning the output.  

**Constraints**  
1 ≤ _N_ ≤ 2\*10<sup>5</sup>  

**Sample Input 00**

	111

**Sample Output 00**

	147
    
**Sample Input 01**

	123

**Sample Output 01**

	177
    
**Explanation**  

The subsequence of number 111 are 111, 11 , 11, 11, 1, 1 and 1. Whose sum is 147.

The subsequence of number 123 are 123, 12 , 23, 13, 1, 2 and 3. Whose sum is 177.

Cod sursa

#!/bin/python3

import sys

MOD = 10 ** 9 + 7


def main():
    s = sys.stdin.readline().strip()
    n = len(s)

    pow2 = [1] * (n + 1)
    pow11 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow2[i] = (pow2[i - 1] * 2) % MOD
        pow11[i] = (pow11[i - 1] * 11) % MOD

    ans = 0
    for i, ch in enumerate(s):
        d = ord(ch) - 48
        ans = (ans + d * pow2[i] * pow11[n - 1 - i]) % MOD

    print(ans)


if __name__ == '__main__':
    main()