Дегустация вин

Question

Я потратил почти все время соревнования (3 часа) для решения этой проблемы.Напрасно :( Может быть, вы могли бы помочь мне найти решение.

У группы сотрудников Facebook только что был очень успешный запуск продукта. Чтобы отпраздновать, они решили пойти на дегустацию вин. На винограднике, они решают сыграть в игру. Один человек получает несколько бокалов вина, в каждом из которых содержится свое вино. Каждый бокал вина помечен, чтобы указать вид вина, которое содержится в бокале. После дегустации каждого из вин маркированные бокалыудаляется, и одному и тому же человеку дают бокалы, содержащие те же вина, но без маркировки. Затем человеку необходимо определить, в каком из немаркированных бокалов содержится какое вино. К сожалению, никто в группе не может отличить вина друг от друга, поэтому они просто угадывают случайно.всегда угадывайте разные типы вина для каждого бокала. Если они получают достаточно прав, они выигрывают игру. Вы должны найти количество способов, которыми человек может выиграть, по модулю 1051962371.

Вход
Первая строка ввода - это количество тестов, NКаждая из следующих 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

Answer 1

Вот тот, который не нуждается в предварительных знаниях чисел Rencontres.(Ну, это в основном доказательство формулы из вики, но я все равно решил поделиться ею.)

Сначала найдите f (n): число перестановок n элементов, которые не имеют фиксированного значения.точка.Это просто формулой включения-исключения: число перестановок, которые фиксируют k заданных точек, равно (nk) !, и эти 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) способами, а остальные nk точек могут быть переставлены f (nk) способами.Итак, это C (n, k) f (nk).

Наконец, ответом на проблему является сумма C (g, k) f (gk) по k = c, c + 1,..., г.

Answer 2

Мое решение заключалось в использовании Rencontres Numbers .

Число Rencontres 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).

Теперь, чтобы вычислить h(g,c), нам нужно рассмотреть два случая у j-го стекла.

• Если мы пометим его 1, мы уменьшим проблему до f(g-1,c).
• Если мы пометим его k, у нас будет g-1 вариантов, и проблема уменьшится до h(g-1,c).

Итак, у нас есть h(g,c) = f(g-1,c) + (g-1) * h(g-1,c).

Вот полная программа на Хаскелле, с памяткой и некоторой поддержкой отладки.

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))