Soluție HackerRank pentru Manasa and Sub-sequences, subdomeniul Algebra, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Manasa and Sub-sequences
  • Domeniu: Algebra
  • Limbaj: Python 3

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

Cerință

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 sursă

#!/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()
HackerRank Algebra – Manasa and Sub-sequences