17

Дано mот nшоколада, m,nположительные, выходного число способов , чтобы сломать планку в mn1 по 1 штуки , где каждый разрыв происходит на линии сетки.

Порядок важен. Кусочки также различимы, поэтому две части на каждом конце шоколадной плитки 1 на 3 не эквивалентны.

Например, для блока 2 на 2 имеем:

 _ _            _   _            _   _            _   _
|_‖_|    ->    |‗| |_|    ->    |_| |‗|    ->    |_| |_|
|_‖_|          |_| |_|           _  |_|           _   _
                                |_|              |_| |_|


 _ _            _   _            _   _            _   _
|_‖_|    ->    |_| |‗|    ->    |‗| |_|    ->    |_| |_|
|_‖_|          |_| |_|          |_|  _            _   _
                                    |_|          |_| |_|


 _ _            _ _              _   _            _   _
|‗|‗|    ->    |_‖_|      ->    |_| |_|    ->    |_| |_|
|_|_|           _ _               _ _             _   _
               |_|_|             |_‖_|           |_| |_|


 _ _            _ _               _ _             _   _
|‗|‗|    ->    |_|_|      ->     |_‖_|    ->     |_| |_|
|_|_|           _ _              _   _            _   _
               |_‖_|            |_| |_|          |_| |_|

Следовательно, есть 4 способа разбить плитку шоколада 2 на 2.

правила

Ввод будет двумя целыми числами через функцию ввода, STDIN, командную строку или подобное. Выведите одно число, количество способов разбить плитку шоколада.
Поскольку числа растут довольно быстро, не беспокойтесь, если выходные данные превысят целочисленные пределы вашего языка - ваше представление будет действительным до тех пор, пока алгоритм теоретически работает для всех возможных входных данных.

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

Вывод не зависит от порядка m,n, поэтому контрольные примеры перечислены так, что m <= n.

1 1 -> 1
1 2 -> 1
1 3 -> 2
1 4 -> 6
1 5 -> 24
1 10 -> 362880

2 2 -> 4
2 3 -> 56
2 4 -> 1712
2 5 -> 92800
2 10 -> 11106033743298560

3 3 -> 9408
3 4 -> 4948992
3 5 -> 6085088256
3 10 -> 76209753666310470268511846400

4 4 -> 63352393728

A261964 - это шоколадные числа, расположенные в треугольнике, так что каждый ряд соответствует сумме m+n.

code-golf sequence combinatorics Sp3000
источник

7

Mathematica, 85 байт

f=If[##==1,1,Tr[Sum[Binomial[1##-2,i#-1]f[i,#]f[#2-i,#],{i,#2-1}]&@@@{{##},{#2,#}}]]&

Прецедент

f[4,4]
(* 63352393728 *)

njpipeorgan
источник

3

Python 3, 168 , 156 , 147 байт

Внесены улучшения благодаря чату

f=lambda n:n<1or n*f(n-1);a=lambda m,n,c=lambda m,n:sum(f(m*n-2)/f(i*n-1)/f((m-i)*n-1)*a(i,n)*a(m-i,n)for i in range(1,m)):+(m+n<4)or c(m,n)+c(n,m)

Ungolfed:

f=lambda n:n<1or n*f(n-1) # Factorial
def a(m, n):
    if m+n < 4:
        return 1
    first = 0
    for i in range(1,m):
        first += f(m*n-2) * 1/f(i*n-1) * 1/f((m-i)*n-1) * a(i,n) * a(m-i,n)
    second = 0
    for i in range(1,n):
        second += f(m*n-2) * 1/f(i*m-1) * 1/f((n-i)*m-1) * a(i,m) * a(n-i,m)
    return first + second

Алгоритм был основан на этой статье .

Я мог бы сократить это намного больше, я просто не уверен, где

Кэмерон Аавик
источник

3

R 208 198 байт

f=function(m,n){g=function(i,j){a=0;if(j>1)for(x in 2:j-1)a=a+choose(j*i-2,x*i-1)*M[x,i]*M[j-x,i];a};s=max(m,n);M=matrix(1,s,s);for(i in 1:s)for(j in 1:s)if(i*j>2)M[i,j]=M[j,i]=g(i,j)+g(j,i);M[m,n]}

С отступом, с новыми строками:

f = function(m,n){
    g=function(i,j){
        a = 0
        if(j>1) for(x in 2:j-1) a = a + choose(j*i-2,x*i-1) * M[x,i] * M[j-x,i]
        a
    }
    s = max(m,n)
    M = matrix(1,s,s)
    for(i in 1:s) for(j in 1:s) if(i*j>2) M[i,j] = M[j,i] = g(i,j) + g(j,i)
    M[m,n]
}

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

> f(3,1)
[1] 2
> f(3,2)
[1] 56
> f(3,3)
[1] 9408
> f(4,3)
[1] 4948992
> f(5,3)
[1] 6085088256

plannapus
источник

Теоретически, можно написать более короткую рекурсивную версию ок. 160 байт, но он быстро достигает предела рекурсии по умолчанию, а размер стека защиты по умолчанию и изменение этих значений по умолчанию (соответственно с использованием options(expressions=...)и аргумента --max-ppsize=) приведет к более длинному коду, чем этот.

plannapus

Вы можете сохранить два байта, опуская f=.

Алекс А.

2

Python 2, 135 байт

C=lambda A:sum(C(A[:i]+A[i+1:]+[(c,H),(W-c,H)])for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1
print C([input()])

Вот что я придумал. Это действительно медленно, но вот более быстрая версия (нужна repoze.lru ):

from repoze.lru import lru_cache
C=lru_cache(maxsize=9999)(lambda A:sum(C(tuple(sorted(A[:i]+A[i+1:]+((c,H),(W-c,H)))))for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1)
print C((input(),))

Примеры

$ time python2 chocolate.py <<< 2,5
92800

real    0m2.954s
user    0m0.000s
sys     0m0.015s

$ time python2 chocolate-fast.py <<< 3,5
6085088256

real    0m0.106s
user    0m0.000s
sys     0m0.015s

объяснение

Код определяет функцию, Cкоторая принимает массив частей. Алгоритм таков:

for i,Q in enumerate(A): цикл по массиву частей.
for W,H in(Q,Q[::-1]): рассчитать пути дважды, поворачивая на 90 градусов.
for c in range(1,W): цикл через возможные позиции для разделения.
A[:i]+A[i+1:]+[(c,H),(W-c,H)]: получить список без разделенной части и с двумя новыми частями.
C(…): вызвать функцию снова в этом списке.
sum(…): суммировать результаты для каждого возможного разделения.
or 1Если раскол невозможен, есть только один способ расколоть шоколад.

Наконец, код вызывается с массивом, содержащим входные данные.

PurkkaKoodari
источник

1

ES6, 141 байт

c=(m,n)=>(f=n=>n<2||n*f(n-1),h=(m,n)=>[...Array(m-1)].reduce((t,_,i)=>t+f(m*n-2)/f(++i*n-1)/f((m-i)*n-1)*c(i,n)*c(m-i,n),0),h(m,n)+h(n,m))||1

На основе формулы, найденной @CameronAavik. Ungolfed:

function fact(n) {
    return n < 2 ? 1 : n * f(n - 1);
}
function half(m, n) {
    total = 0;
    for (i = 1; i < m; i++)
        total += fact(m * n - 2) / fact(i * n - 1) / fact((m - i) * n - 1) * choc(i, n) * choc(m - i, n)
    return total;
}
function choc(m, n) {
    total = half(m, n) + half(n, m);
    if (!total) total = 1;
    return total;
}

Нил
источник

Шоколадные номера