Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # bynary indexed tree
- class BIT:
- def __init__(self, n):
- self.n = n
- self.N = 1 << n.bit_length()
- self.data = [0] * (self.N +1)
- def add(self, i, x):
- while i <= self.N:
- self.data[i] += x
- i += i & -i
- def sum(self, i):
- total = 0
- while i > 0:
- total += self.data[i]
- i -= i&-i
- return total
- def search(self, w):
- if w <= 0:
- return 0
- x = 0
- k = self.N >> 1
- while k > 0:
- if x+k <= self.N and self.data[x+k] < w:
- w -= self.data[x+k]
- x += k
- k = k >> 1
- return x+1
- def len(self):
- return self.data[self.N]
- # fast nCr
- def frac(n, r):
- if r < 0 or r > n:
- return 0
- r = min(r, n - r)
- return g1[n] * g2[r] * g2[n - r] % mod
- mod = 10 ** 9 + 7
- N = 10 ** 6
- g1 = [1, 1]
- g2 = [1, 1]
- inverse = [0, 1]
- for i in range(2, N + 1):
- g1.append((g1[-1] * i) % mod)
- inverse.append((-inverse[mod % i] * (mod // i)) % mod)
- g2.append((g2[-1] * inverse[-1]) % mod)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement