Return to Answer

If that's still not fast enough you could try using deque also from collections, and manually updating the set in each cycle of the loop. You can also take advantage of the fact that the number removed from the top of the list on each cycle gives you a clue as to what the next number has to be (higher or lower); and can use a slightly simplified algorithm when dealing with numbers that the programme has added to the list (in which any sequence of k values can contain no duplicates), as opposed to the original pseudo-random list (which may). (Again, the following is untested)

from collections import deque

def get_next(i):
    while i in set_last_k:
        i += 1
    return i
    
for line1, line2 in zip(cases[1::2], cases[2::2]):
    n, k = map(int, line1.split())
    a, b, c, r = map(int, line2.split())
    m = [a]
    for i in xrange(k - 1):
        m.append((b * m[-1] + c) % r)
    last_k = deque(m)
    set_last_k = set(last_k)
    next = get_next(0)
    for j in xrange(min(k, n - k)): # original list - may contain duplicates
        i = next
        removed = last_k.popleft()
        if removed in last_k:
            next = get_next(i+1)
        else:
            set_last_k.remove(removed)
            if removed < i:
                next = removed
            else:
                next = get_next(i+1)
        m.append(i)
        last_k.append(i)
        set_last_k.add(i)
    if n > 2*k:
        for j in xrange(n - 2*k): # extended list - no duplicates
            i = next
            removed = last_k.popleft()
            set_last_k.remove(removed)
            if removed < i:
                next = removed
            else:
                next = get_next(i + 1)
            m.append(i)
            last_k.append(i)
            set_last_k.add(i)
    print len(m), m[-1]

Untested, but using Counter from collections may be quicker than forming a set of the last k values each time, for large values of k and n.

counter = collections.Counter(m)
for j in xrange(n - k):
    i = 0
    while counter[i]:
        i += 1
    counter[m[j]] -= 1
    counter[i] = 1
    m.append(i)

If making the counter takes a long time because k is very large, you could consider making it in 'chunks', reading say the smallest 100 values from m initially then reading another 100 only when i gets larger than the smallest 100.

Untested, but using Counter from collections may be quicker than forming a set of the last k values each time.

counter = collections.Counter(m)
for j in xrange(n - k):
    i = 0
    while counter[i]:
        i += 1
    counter[m[j]] -= 1
    counter[i] = 1
    m.append(i)

If making the counter takes a long time because k is very large, you could consider making it in 'chunks', reading say the smallest 100 values from m initially then reading another 100 only when i gets larger than the smallest 100.

Untested, but using deque and Counter from collections should be quicker than forming a set of the last k values each time, for large values of k and n.

last_k = collections.deque(m)
counter = collections.Counter(m)
for j in xrange(n - k):
    i = 0
    while counter[i]:
        i += 1
    counter[last_k.popleft()] -= 1
    counter[i] += 1
    last_k.append(i)
    m.append(i)

If making the counter takes a long time because k is very large, you could consider making it in 'chunks', reading say the smallest 100 values from m initially then reading another 100 only when i gets larger than the smallest 100.

Untested, but using Counter from collections may be quicker than forming a set of the last k values each time, for large values of k and n.

counter = collections.Counter(m)
for j in xrange(n - k):
    i = 0
    while counter[i]:
        i += 1
    counter[m[j]] -= 1
    counter[i] = 1
    m.append(i)

If making the counter takes a long time because k is very large, you could consider making it in 'chunks', reading say the smallest 100 values from m initially then reading another 100 only when i gets larger than the smallest 100.