葡萄酒品尝问题
我几乎花了所有的时间(3小时)来解决这个问题。(也许你可以帮我找到解决办法。)
一群Facebook员工刚刚推出了非常成功的产品。为了庆祝，他们决定去品酒。在葡萄园，他们决定玩游戏。一个人喝了几杯酒，每一杯都含有不同的酒。每一杯酒都贴上标签，以表示杯子中含有的葡萄酒种类。在品尝了每一种葡萄酒后，标签杯被移除，同一个人被给予含有相同葡萄酒的杯子，但没有贴上标签。然后，该人需要确定哪个未贴标签的玻璃杯中含有哪一种葡萄酒。可悲的是，没有人能区分葡萄酒，所以他们只是随机猜测。他们总是为每一杯猜测不同类型的葡萄酒。如果他们做得对，他们就会赢得比赛。你必须找出多少方法，人可以赢，模1051962371。
输入
输入的第一行是测试用例的数量。接下来的N行每一行都包含一个测试用例，测试用例由两个整数G和C组成，由单个空格分隔。G是酒杯的总数，C是人们必须正确识别才能获胜的最小数量。
约束
N = 20
1 ≤ **G** ≤ 100 1 ≤ **C** ≤ **G** 输出
对于每个测试用例，输出一个包含一个整数的行，这个人可以通过多少方式赢得游戏模块1051962371。
示例输入
5
1 1
4 2
5 5
13 10
14 1
示例输出
1
7
1
651
405146859
回答 4
Stack Overflow用户
发布于 2011-01-23 17:33:23
这是一个不需要事先了解Rencontres数的方法。(嗯，这基本上是维基公式的证明，但我想我还是会分享的。)
首先找到f(n)：没有不动点的n个元素的排列数。用包含排除公式很简单:固定k个给定点的排列数是(N)！，这些k点可以用C(n，k)方式选择。因此，f(n) = n！- C(n,1)(n-1)！+ C(n,2)(n-2)！- C(n,3)(n-3)！+.
现在找出完全有k个不动点的排列数。这些点可以用C(n，k)方式选择，其余的n-k点可以用f(n-k)方式重新排列。所以，它是C(n，k)f()。
最后，这个问题的答案是k= c，c+1，…，g上的C(g，k)f(G)之和。
Stack Overflow用户
发布于 2011-01-23 10:29:43
我的解决方案涉及到Rencontres数的使用。
一个Rencontres数D(n，k)是n个元素的排列数，其中正好有k个元素在它们原来的位置上。这个问题至少要求k个elemenet，所以我只取k，k+1，…，n上的和。
下面是我提交的Python文件(清理之后)：
from sys import stdin, stderr, setrecursionlimit as recdepth
from math import factorial as fact
recdepth(100000)
MOD=1051962371
cache=[[-1 for i in xrange(101)] for j in xrange(101)]
def ncr(n,k):
return fact(n)/fact(k)/fact(n-k)
def D(n,k):
if cache[n][k]==-1:
if k==0:
if n==0:
cache[n][k]=1
elif n==1:
cache[n][k]=0
else:
cache[n][k]= (n-1)*(D(n-1,0)+D(n-2,0))
else:
cache[n][k]=ncr(n,k)*D(n-k,0)
return cache[n][k]
return cache[n][k]
def answer(total, match):
return sum(D(total,i) for i in xrange(match,total+1))%MOD
if __name__=='__main__':
cases=int(stdin.readline())
for case in xrange(cases):
stderr.write("case %d:\n"%case)
G,C=map(int,stdin.readline().split())
print answer(G,C)Stack Overflow用户
发布于 2012-04-08 11:07:38
from sys import stdin, stderr, setrecursionlimit as recdepth
from math import factorial as fact
recdepth(100000)
MOD=1051962371
cache=[[-1 for i in xrange(101)] for j in xrange(101)]
def ncr(n,k):
return fact(n)/fact(k)/fact(n-k)
def D(n,k):
if cache[n][k]==-1:
if k==0:
if n==0:
cache[n][k]=1
elif n==1:
cache[n][k]=0
else:
cache[n][k]= (n-1)*(D(n-1,0)+D(n-2,0))
else:
cache[n][k]=ncr(n,k)*D(n-k,0)
return cache[n][k]
return cache[n][k]
def answer(total, match):
return sum(D(total,i) for i in xrange(match,total+1))%MOD
if __name__=='__main__':
cases=int(stdin.readline())
for case in xrange(cases):
stderr.write("case %d:\n"%case)
G,C=map(int,stdin.readline().split())
print answer(G,C)https://stackoverflow.com/questions/4773325
复制相似问题
腾讯云开发者
