Wine Tasting problem

I've spent 开发者_如何学JAVAalmost all competition time(3 h) for solving this problem. In vain :( Maybe you could help me to find the solution.

A group of Facebook employees just had a very successful product launch. To celebrate, they have decided to go wine tasting. At the vineyard, they decide to play a game. One person is given some glasses of wine, each containing a different wine. Every glass of wine is labelled to indicate the kind of wine the glass contains. After tasting each of the wines, the labelled glasses are removed and the same person is given glasses containing the same wines, but unlabelled. The person then needs to determine which of the unlabelled glasses contains which wine. Sadly, nobody in the group can tell wines apart, so they just guess randomly. They will always guess a different type of wine for each glass. If they get enough right, they win the game. You must find the number of ways that the person can win, modulo 1051962371.

Input

The first line of the input is the number of test cases, N. The next N lines each contain a test case, which consists of two integers, G and C, separated by a single space. G is the total number of glasses of wine and C is the minimum number that the person must correctly identify to win.

Constraints

N = 20

1 ≤ G ≤ 100

1 ≤ C ≤ G

Output

For each test case, output a line containing a single integer, the number of ways that the person can win the game modulo 1051962371.

Example input

5

1 1

4 2

5 5

13 10

14 1

Example output

1

7

1

651

405146859

---

Here's the one that doesn't need the prior knowledge of Rencontres numbers. (Well, it's basically the proof a formula from the wiki but I thought I'd share it anyway.)

First find f(n): the number of permutations of n elements that don't have a fixed point. It's simple by inclusion-exclusion formula: the number of permutations that fix k given points is (n-k)!, and these k points can be chosen in C(n,k) ways. So, f(n) = n! - C(n,1)(n-1)! + C(n,2)(n-2)! - C(n,3)(n-3)! + ...

Now find the number of permutations that have exactly k fixed points. These points can be chosen in C(n,k) ways and the rest n-k points can be rearranged in f(n-k) ways. So, it's C(n,k)f(n-k).

Finally, the answer to the problem is the sum of C(g,k)f(g-k) over k = c, c+1, ..., g.

---

My solution involved the use of Rencontres Numbers.

A Rencontres Number D(n,k) is the number of permutations of n elements where exactly k elements are in their original places. The problem asks for at least k elemenets, so I just took the sum over k, k+1,...,n.

Here's my Python submission (after cleaning up):

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)

---

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)

---

Like everyone else, I computed the function that I now know is Rencontres Numbers, but I derived the recursive equation myself in the contest. Without loss of generality, we simply assume the correct labels of wines are 1, 2, .., g, i.e., not permuted at all.

Let's denote the function as f(g,c). Given g glasses, we look at the first glass, and we could either label it right, or label it wrong.

• If we label it right, we reduce the problem to getting c-1 right out of g-1 glasses, i.e., f(g-1, c-1).
• If we label it wrong, we have g-1 choices for the first glass. For the remaining g-1 glasses, we must get c glasses correct, but this subproblem is different from the f we're computing, because out of the g-1 glasses, there's already a mismatching glass. To be more precise, for the first glass, our answer is j instead of the correct label 1. Let's assume there's another function h that computes it for us.

So we have f(g,c) = f(g-1,c-1) + (g-1) * h(g-1, c).

Now to compute h(g,c), we need to consider two cases at the jth glass.

• If we label it 1, we reduce the problem to f(g-1,c).
• If we label it k, we have g-1 choices, and the problem is reduced to h(g-1,c).

So we have h(g,c) = f(g-1,c) + (g-1) * h(g-1,c).

Here's the complete program in Haskell, with memoization and some debugging support.

import Control.Monad
import Data.MemoTrie
--import Debug.Trace

trace = flip const

add a b = mod (a+b) 1051962371
mul a b = mod (a*b) 1051962371

main = do
  (_:input) <- liftM words getContents
  let map' f [] = []
      map' f (a:c:xs) = f (read a) (read c) : map' f xs
  mapM print $ map' ans input

ans :: Integer -> Integer -> Integer
ans g c = foldr add 0 $ map (f g) [c..g]

memoF = memo2 f
memoH = memo2 h

-- Exactly c correct in g
f :: Integer -> Integer -> Integer
f g c = trace ("f " ++ show (g,c) ++ " = " ++ show x) x
  where x = if c < 0 || g < c then 0
            else if g == c then 1
            else add (memoF (g-1) (c-1)) (mul (g-1) (memoH (g-1) c))

-- There's one mismatching position in g positions
h :: Integer -> Integer -> Integer
h g c = trace ("h " ++ show (g,c) ++ " = " ++ show x) x
  where x = if c < 0 || g < c then 0
            else add (memoF (g-1) c) (mul (g-1) (memoH (g-1) c))