擅长:python、mysql、java
<p>最多经过<code>k+1</code>步后,数组中的最后一个<code>k+1</code>数字将是<code>0...k</code>(按某种顺序)。随后,序列是可预测的:<code>m[i] = m[i-k-1]</code>。因此,解决这个问题的方法是运行幼稚实现的<code>k+1</code>步骤。然后得到一个包含<code>2k+1</code>元素的数组(第一个<code>k</code>是从随机序列生成的,另一个<code>k+1</code>是从迭代生成的)。</p>
<p>现在,最后的k+1元素将无限重复。所以您可以立即返回<code>m[n]</code>的结果:它是<code>m[k + (n-k-1) % (k+1)]</code>。</p>
<p>下面是一些实现它的代码。</p>
<pre><code>import collections
def initial_seq(k, a, b, c, r):
v = a
for _ in xrange(k):
yield v
v = (b * v + c) % r
def find_min(n, k, a, b, c, r):
m = [0] * (2 * k + 1)
for i, v in enumerate(initial_seq(k, a, b, c, r)):
m[i] = v
ks = range(k+1)
s = collections.Counter(m[:k])
for i in xrange(k, len(m)):
m[i] = next(j for j in ks if not s[j])
ks.remove(m[i])
s[m[i-k]] -= 1
return m[k + (n - k - 1) % (k + 1)]
print find_min(97, 39, 34, 37, 656, 97)
print find_min(186, 75, 68, 16, 539, 186)
print find_min(137, 49, 48, 17, 461, 137)
print find_min(1000000000, 100000, 48, 17, 461, 137)
</code></pre>
<p>这四个案例在我的机器上运行了4秒钟,最后一个案例可能是最大的<code>n</code>。</p>