Compte tenu d' une mpar nbarre de chocolat, m,nsortie positive, le nombre de moyens de briser la barre dans mnune par une des pièces , où chaque rupture se produit sur une ligne de grille.

L'ordre est important. Les morceaux se distinguent également, de sorte que les deux morceaux à chaque extrémité d'une barre de chocolat 1 par 3 ne sont pas équivalents.

Par exemple, pour un bloc 2 par 2, nous avons:

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


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


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


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

Il existe donc 4 façons de briser une barre de chocolat 2 par 2.

Règles

• L'entrée sera deux entiers via l'entrée de fonction, STDIN, la ligne de commande ou similaire. Sortie d'un seul numéro, le nombre de façons de briser la barre de chocolat.

• Étant donné que les nombres augmentent assez rapidement, ne vous inquiétez pas si la sortie dépasse les limites entières de votre langue - votre soumission sera valide tant que l'algorithme fonctionnera théoriquement pour toutes les entrées possibles.

Cas de test

La sortie ne dépend pas de l'ordre de m,n, donc les cas de test sont répertoriés de cette façon 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 est les nombres de chocolat disposés dans un triangle de telle sorte que chaque rangée correspond à la somme m+n.

Mathematica, 85 octets

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

Cas de test

f[4,4]
(* 63352393728 *)

Python 3, 168 , 156 , 147 octets

Améliorations apportées grâce au chat

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)

Non golfé:

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

L'algorithme était basé sur cet article .

Je pourrais probablement le réduire beaucoup plus, je ne sais pas où

R, 208 198 octets

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]}

En retrait, avec de nouvelles lignes:

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]
}

Usage:

> 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

Python 2, 135 octets

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

Voici ce que j'ai trouvé. C'est vraiment lent, mais voici une version plus rapide (nécessite 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(),))

Exemples

$ 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

Explication

Le code définit une fonction Cqui prend un tableau de pièces. L'algorithme est en tant que tel:

1. for i,Q in enumerate(A): boucle à travers le tableau de pièces.
2. for W,H in(Q,Q[::-1]): calculez deux fois le chemin en tournant de 90 degrés.
3. for c in range(1,W): boucle à travers les positions possibles pour se diviser.
4. A[:i]+A[i+1:]+[(c,H),(W-c,H)]: obtenir une liste sans le morceau fendu et avec les deux nouveaux morceaux.
5. C(…): appelez à nouveau la fonction sur cette liste.
6. sum(…): additionne les résultats pour chaque division possible.
7. or 1: si aucune division n'est possible, il y a exactement une façon de diviser le chocolat.

Enfin, le code est appelé avec un tableau contenant l'entrée.

ES6, 141 octets

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

Basé sur la formule trouvée par @CameronAavik. Non golfé:

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;
}