El videojuego Transistor presenta un sistema de habilidades muy interesante. Recolecta 16 "Funciones" que puede usar en 16 ranuras diferentes. Lo interesante es que hay 3 tipos de ranuras y cada función se comporta de manera diferente según la ranura en la que la use:

• Hay 4 ranuras pasivas .
• Hay 4 ranuras activas .
• Cada ranura activa tiene 2 ranuras de actualización .

Queremos averiguar cuántos conjuntos de habilidades diferentes nos da.

Sin embargo, algunas combinaciones son equivalentes. En particular, dentro de cada uno de esos grupos de ranuras, la posición específica de una función no importa. Por otro lado, el efecto de una función en un intervalo de actualización no dependen de la función específica utilizada en la matriz de ranura activa.

Por lo tanto, al usar dígitos hexadecimales para representar las Funciones, las siguientes combinaciones son todas equivalentes:

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    2     0     1     3    # Permutation of passive slots.
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     6     4     7    # Permutation of active slots together
Upgrade Slots:   A B   C D   8 9   E F   # with their upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   B A   C D   F E   # Permutation within upgrade slots.

así como cualquier combinación de estos reordenamientos. Tenga en cuenta que en el tercer caso, las ranuras de actualización se intercambiaron junto con las ranuras activas para mantener el mismo efecto general.

Por otro lado, las siguientes combinaciones son todas diferentes del conjunto anterior:

Passive Slots:    4     5     6     7    # Passive slots swapped
Active Slots:     0     1     2     3    # with active slots.
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     4     6     7    # Permutation of active slots without
Upgrade Slots:   8 9   A B   C D   E F   # changing upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 A   9 B   C D   E F   # Permutation between different upgrade slots.

Según mi recuento, eso le da 2,270,268,000 combinaciones posibles (funcionalmente distintas), suponiendo que se usen todas las funciones.

Si tiene menos de 16 funciones a su disposición, algunas de las ranuras permanecerán vacías. Sin embargo, tenga en cuenta que no puede colocar una función en una ranura de actualización si la ranura activa principal está vacía.

El reto

Debes determinar la cantidad de configuraciones posibles dependiendo de cuántas funciones tengas. Además, generalizaré un poco el problema al hacer que el número de ranuras sea variable, para evitar soluciones triviales de codificación.

Escriba un programa o función que, dados dos enteros positivos M ≥ 1y 1 ≤ N ≤ 4M, determine el número de conjuntos de habilidades posibles (funcionalmente distintos) suponiendo que Nse utilicen exactamente diferentes funciones para llenar la mayor cantidad posible de Mespacios pasivos, Mactivos y de 2Mactualización.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Su código debe ser capaz de manejar cualquier entrada hasta M = 8dentro de un minuto en una máquina de escritorio razonable. Hay cierto margen de maniobra en esto, pero debería descartar soluciones de fuerza bruta. En principio, no debería ser un problema resolver ninguna de esas entradas en menos de un segundo.

Este es el código de golf, gana la respuesta más corta (en bytes).

Casos de prueba

Cada caso de prueba está en el formulario M N => Result.

1 1 => 2
1 2 => 4
1 3 => 9
1 4 => 12
2 1 => 2
2 2 => 6
2 3 => 21
2 4 => 78
2 5 => 270
2 6 => 810
2 7 => 1890
2 8 => 2520
3 1 => 2
3 2 => 6
3 3 => 23
3 4 => 98
3 5 => 460
3 6 => 2210
3 7 => 10290
3 8 => 44520
3 9 => 168840
3 10 => 529200
3 11 => 1247400
3 12 => 1663200
4 1 => 2
4 2 => 6
4 3 => 23
4 4 => 100
4 5 => 490
4 6 => 2630
4 7 => 14875
4 8 => 86030
4 9 => 490140
4 10 => 2652300
4 11 => 13236300
4 12 => 59043600
4 13 => 227026800
4 14 => 718918200
4 15 => 1702701000
4 16 => 2270268000
5 1 => 2
5 2 => 6
5 3 => 23
5 4 => 100
5 5 => 492
5 6 => 2672
5 7 => 15694
5 8 => 98406
5 9 => 644868
5 10 => 4306932
5 11 => 28544670
5 12 => 182702520
5 13 => 1101620520
5 14 => 6122156040
5 15 => 30739428720
5 16 => 136670133600
5 17 => 524885961600
5 18 => 1667284819200
5 19 => 3959801445600
5 20 => 5279735260800
6 1 => 2
6 2 => 6
6 3 => 23
6 4 => 100
6 5 => 492
6 6 => 2674
6 7 => 15750
6 8 => 99862
6 9 => 674016
6 10 => 4787412
6 11 => 35304654
6 12 => 265314588
6 13 => 1989295308
6 14 => 14559228684
6 15 => 101830348620
6 16 => 667943115840
6 17 => 4042651092480
6 18 => 22264427465280
6 19 => 110258471363040
6 20 => 484855688116800
6 21 => 1854067032417600
6 22 => 5894824418683200
6 23 => 14025616720315200
6 24 => 18700822293753600
7 1 => 2
7 2 => 6
7 3 => 23
7 4 => 100
7 5 => 492
7 6 => 2674
7 7 => 15752
7 8 => 99934
7 9 => 676428
7 10 => 4849212
7 11 => 36601554
7 12 => 288486132
7 13 => 2349550632
7 14 => 19504692636
7 15 => 162272450340
7 16 => 1328431104000
7 17 => 10507447510560
7 18 => 78942848624640
7 19 => 554967220167360
7 20 => 3604592589998400
7 21 => 21411337810262400
7 22 => 115428212139240000
7 23 => 561247297649438400
7 24 => 2439121536313862400
7 25 => 9283622495827680000
7 26 => 29520583763711040000
7 27 => 70328449554723360000
7 28 => 93771266072964480000
8 1 => 2
8 2 => 6
8 3 => 23
8 4 => 100
8 5 => 492
8 6 => 2674
8 7 => 15752
8 8 => 99936
8 9 => 676518
8 10 => 4852992
8 11 => 36722169
8 12 => 291621462
8 13 => 2418755196
8 14 => 20834571186
8 15 => 184894557705
8 16 => 1672561326150
8 17 => 15217247948760
8 18 => 137122338089880
8 19 => 1204392465876600
8 20 => 10153538495100000
8 21 => 81007229522419200
8 22 => 604136189949692400
8 23 => 4168645459350372000
8 24 => 26403795950145213600
8 25 => 152700324078982680000
8 26 => 803784718213396920000
8 27 => 3838761204861983400000
8 28 => 16503742828841748480000
8 29 => 62545434470667308160000
8 30 => 198853691115980300400000
8 31 => 474189571122722254800000
8 32 => 632252761496963006400000

Estas son todas las entradas que su código debe manejar en un minuto (cada una), pero en principio debería funcionar para entradas más grandes. Puede usar algunos de los siguientes M = 10casos de prueba para verificar que:

10 1 => 2
10 2 => 6
10 3 => 23
10 4 => 100
10 5 => 492
10 6 => 2674
10 7 => 15752
10 8 => 99936
10 9 => 676520
10 10 => 4853104
10 11 => 36727966
10 12 => 291849866
10 13 => 2426074222
10 14 => 21033972388
10 15 => 189645995396
10 16 => 1773525588406
10 17 => 17155884420532
10 18 => 171073929494468
10 19 => 1750412561088334
10 20 => 18258387148774916
10 21 => 192475976310317700
10 22 => 2028834600633220380
10 23 => 21127206177119902860
10 24 => 214639961631544809360
10 25 => 2101478398293813739200
10 26 => 19602967930531817832000
10 27 => 172444768103233181556000
10 28 => 1417975382888905296456000
10 29 => 10820259026484304813416000
10 30 => 76213534343700480310584000
10 31 => 493916052421168703366040000
10 32 => 2941900199368102067135040000
10 33 => 16113144277547868007416960000
10 34 => 81222252655277786422930560000
10 35 => 376309102059179385262246080000
10 36 => 1589579966324953534441910400000
10 37 => 5981477408861097281112374400000
10 38 => 19005991357166148698688124800000
10 39 => 45381652832417130566255318400000
10 40 => 60508870443222840755007091200000

CJam (56 bytes)

q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+

Demostración en línea

N$n$$k$mn$M$$N$

$X$$0 \le X \le M$$N-X$$\frac{N!}{X!(N-X)!}$$N-X$$M$$3$

$λ_0, λ_1, \ldots, λ_k$$λ_0$$λ_1$$\frac{(N-X)!}{λ_0! λ_1! ... λ_k!}$$λ_i = λ_j$$μ_i$3 2 2 1$μ_3 = 1$$μ_2 = 2$$μ_1 = 1$$λ_i$$λ_i$

Entonces, para cada partición, el número de distribuciones de funciones es

El código anterior calcula las particiones usando el mismo enfoque que Dennis (es obvio y breve, aunque no muy escalable) y luego procesa cada partición en una matriz similar a [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]la que puede levantar la función factorial y luego doblar la división.

CJam, 74 67 bytes

q~4@:Mm*:$L|{:+W$\-M),&},f{0-:F1@@{_m!\I-:Nm!/I(m!/*N}fI;Fm!Fe=/}:+

Verifiqué todos los casos de prueba en mi computadora de escritorio utilizando el intérprete de Java . Esto tomó 2.2 segundos para 1 ≤ M ≤ 8 y 3.5 minutos para M = 10 .

Pruebe este violín en el intérprete de CJam o verifique los primeros 84 casos de prueba a la vez .

Idea

En principio, podemos llenar cada ranura activa y sus ranuras de actualización correspondientes con 0 , 1 , 2 o 3 funciones. Para ranuras 4M en total, tomamos todos los vectores V de {0, 1, 2, 3} ^M y filtramos aquellos para los que sum (V)> N (más funciones en ranuras no pasivas que las funciones totales disponibles) o suma ( V) + M <N (no hay suficientes espacios pasivos para funciones no activas). Clasificamos y deduplicamos todos los vectores guardados, ya que el orden de las familias de ranuras no es importante.

Con N funciones y V = (x ₁ ,…, x _M ) funciones en las partes no pasivas de las familias de ranuras, calculamos el número de combinaciones de la siguiente manera:

1. Si x ₁ = 0 , solo hay una posibilidad para esa familia de ranuras.

   Si x ₁ = 1 , hay N posibilidades, ya que tenemos N funciones, y la función debe ir en la ranura activa.

   Si x ₁ = 2 , debemos colocar una función en la ranura activa y otra en una ranura de actualización (no importa cuál). Hay N opciones para el espacio activo y N-1 opciones restantes para el espacio de actualización, lo que da un total de N (N-1) combinaciones.

   Si x ₁ = 3 , hay N opciones para la ranura activa, N - 1 opciones restantes para la primera ranura de actualización y N - 2 para la segunda ranura de actualización. Como las ranuras de actualización no tienen orden, esto cuenta cada combinación dos veces, por lo que hay N (N - 1) (N - 2) combinaciones únicas.

   En cualquier caso, hay N! / ((N - x ₁ )! × (x ₁ - 1)! Combinaciones para esta familia.

2. Hemos usado las funciones x ₁ , por lo tanto, configure N: = N - x ₁ y repita el paso 1 para x ₂ , luego x ₃ , etc.

3. Si V contiene duplicados, el producto de los resultados anteriores habrá contado todas las combinaciones varias veces. Para cada elemento único de V , si ocurre r veces en V , ¡hay r! formas equivalentes de organizar estas familias de ranuras, por lo que el resultado de arriba debe ser dividido por r! .

4. El resultado final es el número de combinaciones únicas para que V .

Para calcular el número total de combinaciones únicas, todo lo que queda por hacer es calcular la suma de los resultados para cada uno de V .

Código

q~        e# Read an evaluate all input from STDIN. Pushes M and N.
4@:M      e# Push 4, rotate the M, and formally save it in M.
m*        e# Push {0, 1, 2, 3}^M.
:$        e# Sort each vector.
L|        e# Perform set union with the empty list (deduplicates).
{         e# For each sorted vector:
  :+      e#   Compute the sum of its coordinates.
  W$\-    e#   Subtract the sum from N (bottom of the stack).
  M),&    e#   Push [0 ... M] and intersect.
},        e# If the intersection was not empty, keep the vector.
f{        e# For each kept vector, push N and V; then:
  0-:F    e#   Save the non-zero elements of V in F.
  1@@     e#   Push 1 (accumulator), and rotate N and F on top of it.
  {       e#   For each I in F:
    _m!   e#     Push I and push factorial(I).
    \I-:N e#     Subtract I from N and update N.
    m!/   e#     Divide factorial(N) (original N) by factorial(N) (updated N).
    I(m!/ e#     Divide the quotient by factorial(I - 1).
    *     e#    Multiply the accumulator by the resulting quotient.
    N     e#    Push N for the next iteration.
  }fI     e#
  ;       e#   Pop N.
  Fm!     e#   Push all non-unique permutations of F.
  Fe=     e#   Count the number of times F appears.
  /       e#   Divide the accumulator by the result.
}         e#
:+        e# Add all resulting quotients.