Wine tasting problem

Question

I spent almost the entire time of the competition (3 hours) to solve this problem. In vain :( Maybe you could help me find a solution.

The Facebook team had a very successful product launch. To celebrate this, they decided to go on a wine tasting. In the vineyard, they decided to play a game. One person is given some glasses of wine, each of which contains a different wine. Each glass of wine is labeled to indicate the type of wine that contains glass. After tasting each of the wines, the labeled glasses are removed, and the same person is given glasses containing the same wines, but unmarked. Then the person needs to determine which of the unlabeled glasses contains wine. Unfortunately, no one in the group can share the wines, so they just guess at random. They will always guess the different type of wine for each glass. If they get enough rights, they will win the game. You must find the number of ways that a person can win,modulo 1051962371.

Input
The first line of input is the number of test cases, N. The next N lines contain a test case consisting 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 amount that a person must correctly identify in order to win.

Limitations
  N = 20
  1 ≤ G ≤ 100
  1 ≤ C ≤ G

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

Input example
5
1 1
4 2
5 5
13 10
14 1

1
7
1
651
405146859

Answer 1

, Rencontres. (, , , .)

f (n): n , . -: , k , (n-k)!, 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 (n-k).

, C (g, k) f (g-k) k = c, c + 1,..., g.

Answer 2

Rencontres Numbers.

A Rencontres Number D (n, k) - n , k . k , 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)

Answer 3

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)

Answer 4

, , , Rencontres Numbers, . , 1, 2, .., g, .. .

f(g,c). g , , , .

• , c-1 g-1, .. f(g-1, c-1).
• , g-1 . g-1 c, f, , g-1 . , j 1. , h, .

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

Now, to calculate h(g,c), we need to consider two cases on the jth stack .

• If we denote it 1, we reduce the problem to f(g-1,c).
• If we denote it k, we have a choice g-1, and the problem boils down to h(g-1,c).

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

Here's the full 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 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))