回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我在用python解决facebook hackercup上的<a href="https://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420" rel="nofollow noreferrer">^{<cd1>}</a>问题,我的代码对于示例输入很好,但是对于大型输入(10^9),需要几个小时才能完成。</p>
<p>那么,有没有可能用python不能在6分钟内计算出这个问题的解决方案呢?或者是我的方法太差了?</p>
<p><strong>问题陈述</strong>:</p>
<p>发出笑脸后,约翰决定玩数组。你知道黑客喜欢玩数组吗?John有一个基于零的索引数组<code>m</code>,它包含<code>n</code>非负整数。然而,他只知道数组的第一个<code>k</code>值,他想找出其余的值。</p>
<p>John知道以下几点:对于每个索引<code>i</code>,其中<code>k <= i < n</code>,<code>m[i]</code>是最小的非负整数,它是<code>m</code>的前一个<code>*k*</code>值中包含的<em>而不是</em>。</p>
<p>例如,如果<code>k = 3</code>、<code>n = 4</code>和<code>m</code>的已知值是<code>[2, 3, 0]</code>,他可以计算出<code>m[3] = 1</code>。</p>
<p>约翰正忙于使世界变得更加开放和联系起来,因此,他没有时间去了解阵列的其余部分。你的任务是帮助他。</p>
<p>给定<code>m</code>的第一个<code>k</code>值,计算该数组的第n个值。(即<code>m[n - 1]</code>)。</p>
<p>由于<code>n</code>和<code>k</code>的值可能非常大,我们使用伪随机数生成器来计算<code>m</code>的第一个<code>k</code>值。给定正整数<code>a</code>、<code>b</code>、<code>c</code>和<code>r</code>,可以如下计算<code>m</code>的已知值:</p>
<pre><code>m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k
</code></pre>
<p>输入</p>
<ul>
<li><p>第一行包含一个整数T(T<;=20),测试数
案例。</p></li>
<li><p>接下来是T测试用例,每个测试用例由2行组成。</p></li>
<li><p>每个测试用例的第一行包含两个空格分隔的整数,
<code>n</code>,<code>k</code>(<code>1 <= k <= 10^5</code>,<code>k < n <= 10^9</code>)。</p></li>
<li><p>每个测试用例的第二行包含4个空格分隔的整数
<code>a</code>,<code>b</code>,<code>c</code>,<code>r</code>(0<;=a,b,c<;=10^9,1<;=r<;=10^9)。</p></li>
</ul>
<p>我尝试了两种方法,但都未能在6分钟内返回结果,下面是我的两种方法:</p>
<p>首先:</p>
<pre><code>import sys
cases=sys.stdin.readlines()
def func(line1,line2):
n,k=map(int,line1.split())
a,b,c,r =map(int,line2.split())
m=[None]*n #initialize the list
m[0]=a
for i in xrange(1,k): #set the first k values using the formula
m[i]= (b * m[i - 1] + c) % r
#print m
for j in range(0,n-k): #now set the value of m[k], m[k+1],.. upto m[n-1]
temp=set(m[j:k+j]) # create a set from the K values relative to current index
i=-1 #start at 0, lowest +ve integer
while True:
i+=1
if i not in temp: #if that +ve integer is not present in temp
m[k+j]=i
break
return m[-1]
for ind,case in enumerate(xrange(1,len(cases),2)):
ans=func(cases[case],cases[case+1])
print "Case #{0}: {1}".format(ind+1,ans)
</code></pre>
<p>第二:</p>
<pre><code>import sys
cases=sys.stdin.readlines()
def func(line1,line2):
n,k=map(int,line1.split())
a,b,c,r =map(int,line2.split())
m=[None]*n #initialize
m[0]=a
for i in xrange(1,k): #same as above
m[i]= (b * m[i - 1] + c) % r
#instead of generating a set in each iteration , I used a
# dictionary this time.
#Now, if the count of an item is 0 then it
#means the item is not present in the previous K items
#and can be added as the min value
temp={}
for x in m[0:k]:
temp[x]=temp.get(x,0)+1
i=-1
while True:
i+=1
if i not in temp:
m[k]=i #set the value of m[k]
break
for j in range(1,n-k): #now set the values of m[k+1] to m[n-1]
i=-1
temp[m[j-1]] -= 1 #decrement it's value, as it is now out of K items
temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1 # new item added to the current K-1 items
while True:
i+=1
if i not in temp or temp[i]==0: #if i not found in dict or it's val is 0
m[k+j]=i
break
return m[-1]
for ind,case in enumerate(xrange(1,len(cases),2)):
ans=func(cases[case],cases[case+1])
print "Case #{0}: {1}".format(ind+1,ans)
</code></pre>
<p>第二种方法中的最后一个for循环也可以写成:</p>
<pre><code>for j in range(1,n-k):
i=-1
temp[m[j-1]] -= 1
if temp[m[j-1]]==0:
temp.pop(m[j-1]) #same as above but pop the key this time
temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1
while True:
i+=1
if i not in temp:
m[k+j]=i
break
</code></pre>
<p>样本输入:</p>
<pre><code>5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46
</code></pre>
<p>输出:</p>
<pre><code>Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12
</code></pre>
<p>我已经试过了,但是还没有人回答。</p>