Fancy Sequence LeetCode solution in Python

1
def egcd(a, b):
2
    if a == 0:
3
        return (b, 0, 1)
4
    else:
5
        g, y, x = egcd(b % a, a)
6
        return (g, x - (b // a) * y, y)
7

8

9
def modinv(a, m):
10
    g, x, y = egcd(a, m)
11
    return x % m
12

13

14
mod = 1000000007
15

16

17
class Fancy(object):
18

19
    def __init__(self):
20
        self.seq = []
21
        self.addC = 0
22
        self.mulC = 1
23

24
    def append(self, val):
25
        """
26
        :type val: int
27
        :rtype: None
28
        """
29
        self.seq.append([val, self.mulC, self.addC])
30

31
    def addAll(self, inc):
32
        """
33
        :type inc: int
34
        :rtype: None
35
        """
36
        self.addC = (self.addC % mod + inc % mod) % mod
37

38
    def multAll(self, m):
39
        """
40
        :type m: int
41
        :rtype: None
42
        """
43
        self.mulC = (self.mulC % mod * m % mod) % mod
44
        self.addC = (self.addC % mod * m % mod) % mod
45

46
    def getIndex(self, idx):
47
        """
48
        :type idx: int
49
        :rtype: int
50
        """
51
        if idx >= len(self.seq):
52
            return -1
53

54
        mulCo = self.seq[idx][1]
55
        addCo = self.seq[idx][2]
56
        val = self.seq[idx][0]
57

58
        inv = modinv(mulCo, mod)
59
        a = (self.mulC % mod * inv % mod) % mod
60
        val = (val % mod * a % mod) % mod
61
        b = (addCo % mod * a % mod) % mod
62
        val = (val % mod - b % mod) % mod
63
        val = (val % mod + self.addC % mod) % mod
64

65
        return val