O videogame Transistor possui um sistema de habilidades muito interessante. Você coleta 16 "Funções" que podem ser usadas em 16 slots diferentes. O interessante é que existem 3 tipos de slots e cada função se comporta de maneira diferente de acordo com o slot em que você o usa:

• Existem 4 slots passivos .
• Existem 4 slots ativos .
• Cada slot ativo possui 2 slots de atualização .

Queremos descobrir quantas habilidades diferentes isso nos dá.

No entanto, algumas combinações são equivalentes. Em particular, dentro de cada um desses grupos de slots, a posição específica de uma Função não importa. Por outro lado, o efeito de uma função em um slot de atualização não dependem da função específica usada no pai Ativo slot.

Portanto, usando dígitos hexadecimais para substituir as Funções, as seguintes combinações são 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.

bem como qualquer combinação desses rearranjos. Observe que, no terceiro caso, os slots de atualização foram trocados com os slots ativos para manter o mesmo efeito geral.

Por outro lado, as seguintes combinações são todas diferentes do conjunto acima:

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.

Pela minha conta, isso fornece 2.270.268.000 combinações possíveis (funcionalmente distintas), assumindo que todas as funções sejam usadas.

Se você tiver menos de 16 funções à sua disposição, alguns dos slots permanecerão vazios. No entanto, observe que você não pode colocar uma função em um slot de atualização se o slot ativo pai estiver vazio.

O desafio

Você deve determinar o número de configurações possíveis, dependendo de quantas funções você possui. Além disso, generalizarei um pouco o problema, tornando o número de slots variável, a fim de evitar soluções triviais de codificação.

Escreva um programa ou função que, dados dois inteiros positivos M ≥ 1e 1 ≤ N ≤ 4M, determine o número de conjuntos de habilidades possíveis (funcionalmente distintos), assumindo que Nfunções exatamente diferentes sejam usadas para preencher o maior número possível de slots Mpassivos, Mativos e de 2Mupgrade.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Seu código deve ser capaz de lidar com qualquer entrada até e inclusive M = 8em um minuto em uma máquina de desktop razoável. Há alguma margem de manobra nisso, mas deve excluir soluções de força bruta. Em princípio, não deve ser um problema resolver qualquer uma dessas entradas em menos de um segundo.

Isso é código de golfe, a resposta mais curta (em bytes) vence.

Casos de teste

Cada caso de teste está no formulário 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

Essas são todas as entradas que seu código deve manipular dentro de um minuto (cada), mas, em princípio, deve funcionar para entradas maiores. Você pode usar alguns dos seguintes M = 10casos de teste para verificar se:

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!:/}:+

Demonstração online

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$

Portanto, para cada partição, o número de distribuições de funções é

O código acima calcula as partições usando a mesma abordagem que Dennis (é óbvio e curto, embora não seja muito escalável) e, em seguida, processa cada partição em uma matriz semelhante à [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]qual pode levantar a função fatorial e depois dobrar a divisão.

CJam, 74 67 bytes

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

Eu verifiquei todos os casos de teste no meu computador desktop usando o interpretador Java . Isso levou 2,2 segundos para 1 ≤ M ≤ 8 e 3,5 minutos para M = 10 .

Experimente este violino no intérprete CJam ou verifique os primeiros 84 casos de teste de uma só vez .

Idéia

Em princípio, podemos preencher cada slot ativo e seus slots de atualização correspondentes com 0 , 1 , 2 ou 3 funções. Para slots de 4M no total, pegamos todos os vetores V de {0, 1, 2, 3} ^M e filtramos aqueles cuja soma (V)> N (mais funções em slots não passivos que o total de funções disponíveis) ou soma ( V) + M <N (não há slots passivos suficientes para funções não ativas). Classificamos e desduplicamos todos os vetores mantidos, uma vez que a ordem das famílias de slots não é importante.

Com funções N e funções V = (x ₁ ,…, x _M ) nas partes não passivas das famílias de slots, calculamos o número de combinações da seguinte forma:

1. Se x ₁ = 0 , existe apenas uma possibilidade para essa família de slots.

   Se x ₁ = 1 , existem N possibilidades, uma vez que temos N funções, e a função deve estar no slot ativo.

   Se x ₁ = 2 , devemos colocar uma função no slot ativo e outra em um slot de atualização (não importa qual). Existem N opções para o slot ativo e N-1 para o slot de atualização, fornecendo um total de combinações de N (N-1) .

   Se x ₁ = 3 , existem N opções para o slot ativo, N-1 para o primeiro slot de atualização e N-2 para o segundo slot de atualização. Como os slots de atualização não têm ordem, isso conta todas as combinações duas vezes; portanto, existem N (N-1) (N-2) combinações únicas.

   De qualquer forma, existem N! / ((N - x ₁ )! × (x ₁ - 1)! Combinações para esta família.

2. Usamos funções x ₁ , então defina N: = N - x ₁ e repita a etapa 1 para x ₂ , depois x ₃ , etc.

3. Se V contiver duplicatas, o produto dos resultados acima terá contado todas as combinações várias vezes. Para cada elemento exclusivo de V , se ocorrer r vezes em V , haverá r! maneiras equivalentes de organizar essas famílias de slots, portanto o resultado acima deve ser dividido por r! .

4. O resultado final é o número de combinações únicas para que V .

Para calcular o número total de combinações exclusivas, tudo o que resta a fazer é calcular a soma dos resultados para cada 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.