G. Strange Nim Game solution code

G. Strange Nim Game solution code 

In Python3 language 

👇

import sys
MOD = 10**9 + 7
 
def main():
    sys.setrecursionlimit(1 << 25)
    max_x = 200000
    grundy = [0] * (max_x + 1)
 
    for x in range(1, max_x + 1):
        digits = set()
        tmp = x
        while tmp > 0:
            d = tmp % 10
            if d != 0:
                digits.add(d)
            tmp = tmp // 10
        s = set()
        for d in digits:
            if x >= d:
                s.add(grundy[x - d])
        mex = 0
        while mex in s:
            mex += 1
        grundy[x] = mex
 
    max_pow = 2 * 10**5 + 30
    pow2 = [1] * (max_pow + 1)
    for i in range(1, max_pow + 1):
        pow2[i] = (pow2[i-1] * 2) % MOD
 
    class SegmentTreeNode:
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.left = None
            self.right = None
            self.basis = [0] * 30
            self.count = 0  # Total elements in the interval
 
        def update_from_value(self, val):
            self.basis = [0] * 30
            tmp = val
            for i in reversed(range(30)):
                if (tmp >> i) & 1:
                    if self.basis[i] == 0:
                        self.basis[i] = tmp
                        break
                    else:
                        tmp ^= self.basis[i]
                if tmp == 0:
                    break
            self.count = 1  # Each leaf node represents one element
 
        def merge_children(self):
            left = self.left
            right = self.right
            self.basis = left.basis.copy()
            for i in range(30):
                if right.basis[i] != 0:
                    tmp = right.basis[i]
                    for j in reversed(range(30)):
                        if (tmp >> j) & 1:
                            if self.basis[j] == 0:
                                self.basis[j] = tmp
                                break
                            else:
                                tmp ^= self.basis[j]
                        if tmp == 0:
                            break
            self.count = left.count + right.count
 
    def build(l, r, arr):
        node = SegmentTreeNode(l, r)
        if l == r:
            val = arr[l-1]
            node.update_from_value(val)
        else:
            mid = (l + r) // 2
            node.left = build(l, mid, arr)
            node.right = build(mid + 1, r, arr)
            node.merge_children()
        return node
 
    def update(node, idx, val):
        if node.l == node.r == idx:
            node.update_from_value(val)
            return
        if idx <= node.left.r:
            update(node.left, idx, val)
        else:
            update(node.right, idx, val)
        node.merge_children()
 
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    grundy_A = [grundy[x] for x in A]
    root = build(1, N, grundy_A)
 
    Q = int(sys.stdin.readline())
    current_basis = [0] * 30
    current_count = 0
 
    def query(node, l, r):
        nonlocal current_basis, current_count
        if node.r < l or node.l > r:
            return
        if l <= node.l and node.r <= r:
            current_count += node.count
            for i in range(30):
                x = node.basis[i]
                if x != 0:
                    tmp = x
                    for j in reversed(range(30)):
                        if (tmp >> j) & 1:
                            if current_basis[j] == 0:
                                current_basis[j] = tmp
                                break
                            else:
                                tmp ^= current_basis[j]
                        if tmp == 0:
                            break
            return
        query(node.left, l, r)
        query(node.right, l, r)
 
    for _ in range(Q):
        parts = sys.stdin.readline().split()
        if not parts:
            continue
        if parts[0] == '1':
            L = int(parts[1])
            R = int(parts[2])
            current_basis = [0] * 30
            current_count = 0
            query(root, L, R)
            t = R - L + 1
            r = sum(1 for x in current_basis if x != 0)
            ans = (pow2[t] - pow2[t - r]) % MOD
            print(ans)
        else:
            i = int(parts[1])
            x = int(parts[2])
            new_g = grundy[x]
            update(root, i, new_g)
 
if __name__ == "__main__":
    main()