Время для еще одной простой задачи, в которой могут участвовать все!

Полиномиальная теорема гласит:

Выражение в скобках - это множитель, определяемый как:

Разрешение членам k _i охватывать все целочисленные разбиения n дает n-й уровень m -симплекса Паскаля . Ваша задача - вычислить этот коэффициент.

задача

Напишите программу или функцию, которая принимает m чисел, n , k ₁ , k ₂ , ..., k _m-1 и выводит или возвращает соответствующий коэффициент многочлена. Ваша программа может дополнительно принять m в качестве дополнительного аргумента, если это необходимо. Обратите внимание, что k _m не на входе.

• Эти числа могут быть введены в любом понравившемся формате, например, сгруппированы в списки или закодированы в унарном виде, или как угодно, если фактическое вычисление коэффициента многочлена выполняется вашим кодом, а не процессом кодирования.

• Формат вывода также гибкий.

• Весь код должен выполняться менее чем за одну минуту для n и m до 1000.

• Не беспокойтесь о целочисленном переполнении.

• Встроенные модули, предназначенные для вычисления коэффициента многочлена, не допускаются.

• Применяются стандартные лазейки.

счет

Это код гольф: выигрывает самое короткое решение в байтах.

Контрольные примеры

Input: 3, [2, 0]
Output: 3

Input: 3, [1, 1]
Output: 6

Input: 11, [1, 4, 4]
Output: 34650

Input: 4, [1,2]
Output: 12

Input: 15, [5,4,3,2]
Output: 37837800

Input: 95, [65,4,4]
Output: 1934550571913396675776550070308250

Input: 32, [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
Output: 4015057936610313875842560000000

Input: 15, [3,3,3,3]
Output: 168168000

Input: 1000, [10,10,10,10,10,10,10,10,10,10,100,100,100,100,100,100,100,100]
Output: 1892260836114766064839886173072628322819837473493540916521650371620708316292211493005889278395285403318471457333959691477413845818795311980925098433545057962732816261282589926581281484274178579110373517415585990780259179555579119249444675675971136703240347768185200859583936041679096016595989605569764359198616300820217344233610087468418992008471158382363562679752612394898708988062100932765563185864346460326847538659268068471585720069159997090290904151003744735224635733011050421493330583941651019570222984959183118891461330718594645532241449810403071583062752945668937388999711726969103987467123014208575736645381474142475995771446030088717454857668814925642941036383273459178373839445456712918381796599882439216894107889251444932486362309407245949950539480089149687317762667940531452670088934094510294534762190299611806466111882595667632800995865129329156425174586491525505695534290243513946995156554997365435062121633281021210807821617604582625046557789259061566742237246102255343862644466345335421894369143319723958653232683916869615649006682399919540931573841920000000000000

Input: 33, [17]
Output: 1166803110

Input: 55, [28]
Output: 3824345300380220

Желе , 7 6 байт

;_/!:/

Смотри, ма, нет Юникода! Эта программа принимает в качестве входных данных один список с n в первом индексе.

Попробуйте онлайн! или проверьте все тестовые случаи одновременно .

Как это работает

;_/!:/ Input: A (list)

 _/    Reduce A by subtraction. This subtracts all other elements from the first.
;      Concatenate A with the result to the right.
   !   Apply factorial to all numbers in the resulting list.
    :/ Reduce the result by division. This divides the first element by the others.

CJam, 11 байт

l~_:-+:m!:/

Ввод в виде единого списка с nпервым:

[95 65 4 4]

Это ручки входы до nи m1000 довольно много мгновенно.

Проверьте это здесь.

объяснение

l~  e# Read a line of input and evaluate it.
_   e# Duplicate.
:-  e# Fold subtraction over the list. A fold is essentially a foreach loop that starts
    e# from the second element. Hence, this subtracts all the k_i from n, giving k_m.
+   e# Append k_m to the list.
:m! e# Compute the factorial of each element in the list.
:/  e# Fold division over the list. Again, this divides n! by each of the k_i!.

MATL , 21 15 байт

Давайте использовать функцию log-gamma . Это позволяет избежать внутреннего переполнения, работая с логарифмами факториалов, а не с самими факториалами.

1+ZgiO$Gs-h1+Zgs-ZeYo

Это работает в текущей версии (9.2.2) языка / компилятора, которая является более ранней, чем эта проблема.

Входные данные: сначала число, затем числовой вектор. Результат создается как a double, который ограничивает максимальную производительность где-то рядом 2^52.

пример

>> matl 1+ZgiO$Gs-h1+Zgs-ZeYo
> 15
> [5 4 3 2]
37837800

объяснение

1+       % implicit input (number). Add 1
Zg       % log-gamma function
i        % input (numeric vector).
0$G      % push both inputs
s-       % sum the second input (vector) and subtract from first
h1+      % append to vector. Add 1
Zg       % log-gamma function, element-wise on extended vector
s        % sum of results
-        % subtract from previous result of log-gamma
Ze       % exponential
Yo       % round. Implicit display

PowerShell, 91 74 байта

_{Woo! Мой сотый ответ на PPCG!}

param($n,$k)(1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)

Уф. Не собираюсь выигрывать кратчайший код, это точно. Тем не менее, использует несколько хитрых трюков с диапазонами. _{И это, вероятно, полный бред для всех, кто не знаком с PowerShell.}

объяснение

Сначала мы берем ввод с param($n,$k)и ожидаем, $kчто он будет массивом, например .\compute-the-multinomial-coefficient.ps1 11 @(1,4,4).

Начнем с числителя (все слева от /). Это просто диапазон 1..$n, который был -joinотредактирован вместе с *и затем оценен iexдля вычисления факториала (то есть 1*2*3*...*$n).

Затем мы зацикливаемся $k|%{...}и на каждой итерации вычитаем текущее значение ( $_из $nкоторого мы больше не заботимся), чтобы сформулировать его $k_mпозже. Кроме того, мы генерируем диапазон 1..$k_iкаждой итерации, который остается на конвейере. Эти объекты конвейера объединяются в массив со вторым выражением, range 1..$n(который находится $k_mв этой точке). Все это, в конечном итоге, обрабатывается -joinвместе с *оценкой iex, аналогично числителю (это работает потому x! * y! = 1*2*3*...*x * 1*2*3*...*y, что нас не интересует индивидуальный порядок).

Наконец, /случается, числитель делится на знаменатель и выводится.

Правильно обрабатывает выходные данные для больших чисел, поскольку мы не приводим явным образом какие-либо переменные как какие-либо конкретные типы данных, поэтому PowerShell будет автоматически преобразовывать типы данных на лету по мере необходимости. Для больших чисел выходные данные через научную запись лучше сохраняют значимые цифры при повторном приведении типов данных. Например, .\compute-the-multinomial-coefficient.ps1 55 @(28)будет выводить 3.82434530038022E+15. Я предполагаю, что все будет в порядке, учитывая, что «формат вывода такой же гибкий» задан в вызове и в комментариях квинтопии «Если конечный результат может вписаться в искомо поддерживаемые целочисленные типы, то результат должен быть точным. нет никаких ограничений на то, что может быть выведено ".

---

альтернативно

В зависимости от решения о форматировании вывода, следующие в 92 байта

param($n,$k)((1..$n-join'*'|iex)/(($k|%{$n-=$_;1..$_})+(1..$n)-join'*'|iex)).ToString('G17')

Что же , как и выше, просто использует явный вывод форматирования с .ToString('G17')для достижения требуемого количества цифр. Для 55 @(28)этого будет выходной3824345300380220.5

---

Edit1 - Сэкономил 17 байт, избавившись от него $dи просто вычислив его напрямую, а также избавившись от вычисления $k_m, связав его во время цикла $k
Edit2 - Добавлена ​​альтернативная версия с явным форматированием

APL (Dyalog Extended) , 9 байт

×/2!/+\⍛,

Попробуйте онлайн!

Используя идею из моего APL ответа на еще одну проблему, которая включает в себя многочлены .

Неявная функция, левый аргумент которой является списком k, а правый аргумент - n. Тестовые случаи проверяют, соответствует ли это решению Адама, когда левый и правый аргументы перевернуты.

Как это работает

×/2!/+\⍛,
     +\    ⍝ Cumulative sum of k's (up to m-1'th element)
       ⍛,  ⍝ Append n (sum of k_1 to k_m)
  2!/      ⍝ Binomial of consecutive pairs
×/         ⍝ Product

$$\frac{(k_1 + k_2 + \cdots + k_m)!}{k_1! k_2! \cdots k_m!} = \frac{(k_1 + k_2)!}{k_1! k_2!} \times \frac{(k_1 + k_2 + \cdots + k_m)!}{(k_1 + k_2)! k_3! \cdots k_m!}$$

$$= \frac{(k_1 + k_2)!}{k_1! k_2!} \times \frac{(k_1 + k_2 + k_3)!}{(k_1 + k_2)! k_3!} \times \frac{(k_1 + k_2 + \cdots + k_m)!}{(k_1 + k_2 + k_3)! \cdots k_m!}$$

$$= \cdots = \binom{k_1 + k_2}{k_1} \binom{k_1 + k_2 + k_3}{k_1 + k_2} \cdots \binom{k_1 + \cdots + k_m}{k_1 + \cdots + k_{m-1}}$$

Mathematica, 26 байтов

#!/Times@@({#-+##2,##2}!)&

Пример:

In[1]:= #!/Times@@({#-+##2,##2}!)&[95,65,4,4]

Out[1]= 1934550571913396675776550070308250

Питон 3, 93 91

Спасибо Деннису и FryAmTheEggman .

f=lambda x:0**x or x*f(x-1)
def g(n,k):
    r=f(n)
    for i in k:r//=f(i)
    return r//f(n-sum(k))

nкак целое число, kкак итеративный.

Ungolfed:

import functools #cache

@functools.lru_cache(maxsize=None) #cache results to speed up calculations
def factorial(x):
    if x <= 1: return 1
    else: return x * factorial(x-1)

def multinomial(n, k):
    ret = factorial(n)
    for i in k: ret //= factorial(i)
    km = n - sum(k)
    return ret//factorial(km)

APL (Dyalog Unicode) , 16 байтов ^SBCS

Всецело основано на математическом мастерстве моего коллеги Маршалла .

Анонимная инфиксная функция. Принимает k в качестве правого аргумента и n в качестве левого аргумента.

{×/⍵!⍺-+\¯1↓0,⍵}

Попробуйте онлайн!

{... } анонимная лямбда; ⍺левый аргумент ( n ) и ⍵правый аргумент ( k )

 0,⍵ ставить ноль до k

 ¯1↓ выбросить последний элемент из этого

 +\ накопленная сумма этого

 ⍺- вычесть это из п

 ⍵! ( ^k ) что

 ×/ продукт этого

PARI / GP, 43 байта

Довольно просто; Помимо форматирования, версия без заглядывания вполне может быть идентична.

m(n,v)=n!/prod(i=1,#v,v[i]!)/(n-vecsum(v))!

Matlab 48 байтов

Вам нужно установить , formatчтобы longзаранее , чтобы получить более высокую точность. Тогда это довольно просто:

@(n,k)factorial(n)/prod(factorial([k,n-sum(k)]))

ans(95, [65,4,4])
ans =

 1.934550571913395e+33

Pyth, 10 байт

/F.!MaQ-FQ

Попробуйте онлайн: демонстрация

Объяснение:

/F.!MaQ-FQ   implicit: Q = input list
       -FQ   reduce Q by subtraction
     aQ      append the result to Q
  .!M        compute the factorial for each number
/F           reduce by division

J, 16 байт

[(%*/)&:!],(-+/)

использование

Для больших значений используется суффикс xдля обозначения целых чисел с расширенной точностью.

   f =: [(%*/)&:!],(-+/)
   11 f 1 4 4
34650
   15x f 5 4 3 2
37837800

объяснение

[(%*/)&:!],(-+/)  Input: n on LHS, A on RHS
             +/   Reduce A using addition
            -     Subtract that sum from n, this is the missing term
         ]        Get A
          ,       Append the missing term to A to make A'
[                 Get n
      &:!         Take the factorial of n and each value in A'
   */             Reduce using multiplication the factorials of A'
  %               Divide n! by that product and return

05AB1E , 8 байтов

Ƹ«!R.«÷

Попробуйте онлайн! Объяснение:

Æ           Subtract all the elements from the first
 ¸«         Append to the original list
   !        Take the factorial of all the elements
    R.«÷    Reduce by integer division

Кажется, я не могу найти лучшие способы выполнить шаг 2 или шаг 4.

APL (Dyalog Unicode) , 17 байт

⊢∘!÷(×/∘!⊣,⊢-1⊥⊣)

Попробуйте онлайн!

Инфиксная молчаливая функция (спасибо @ Adám за 2 байта, которые она сохраняет.)

---

APL (Dyalog Unicode) , 19 байт

{(!⍺)÷×/!(⍺-+/⍵),⍵}

Попробуйте онлайн!

Инфикс Dfn.

Обе функции выше вычисляют данную формулу.

Haskell , 59 58 байт

f n=product[1..n]
n#k=foldl((.f).div)(f n)k`div`f(n-sum k)

Попробуйте онлайн!

Спасибо BMO за сохранение 1 байта!

Clojure, 70 байт

#(let[a apply](a /(map(fn[x](a *(map inc(range x))))(conj %(a - %)))))

Создает анонимную функцию, принимающую все аргументы как один список, с nпервым.

30 символов «впустую», просто определяя чертову факториальную функцию. Ну что ж.

Perl 6 ,  52  50 байт

->\n,\k{[*](1..n)div[*] ([*] 1..$_ for |k,[-] n,|k)}

Попробуй это

->\n,\k{[*](1..n)/[*] ([*] 1..$_ for |k,[-] n,|k)}

Проверьте это (результат - Rational с знаменателем 1)

Expanded:

->     # pointy block lambda
  \n,
  \k
{
    [*]( 1 .. n )   # factorial of ｢n｣

  /                 # divide (produces Rational)

    [*]             # reduce the following using &infix:«*»

      (
          [*] 1..$_ # the factorial of

        for         # each of the following

          |k,       # the values of ｢k｣ (slipped into list)
          [-] n,|k  # ｢n｣ minus the values in ｢k｣
      )
}