Wine Tasting problem

Question

I've spent almost 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

Answer 1

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.

Answer 2

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)