Le jeu vidéo Transistor dispose d'un système de capacités très intéressant. Vous collectez 16 "Fonctions" que vous pouvez utiliser dans 16 emplacements différents. Ce qui est intéressant, c'est qu'il existe 3 types de slots et chaque fonction se comporte différemment selon le slot dans lequel vous l'utilisez:

• Il y a 4 emplacements passifs .
• Il y a 4 emplacements actifs .
• Chaque emplacement actif dispose de 2 emplacements de mise à niveau .

Nous voulons savoir combien de compétences différentes nous donne.

Cependant, certaines combinaisons sont équivalentes. En particulier, dans chacun de ces groupes d'emplacements, la position spécifique d'une fonction n'a pas d'importance. D'autre part, l'effet d'une fonction dans un emplacement de mise à niveau ne dépend de la fonction spécifique utilisée dans le parent slot actif.

Par conséquent, en utilisant des chiffres hexadécimaux pour remplacer les fonctions, les combinaisons suivantes sont toutes équivalentes:

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.

ainsi que toute combinaison de ces réarrangements. Notez que dans le troisième cas, les emplacements de mise à niveau ont été échangés avec les emplacements actifs pour conserver le même effet global.

D'un autre côté, les combinaisons suivantes sont toutes différentes de l'ensemble ci-dessus:

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.

D'après mes calculs, cela vous donne 2 270 268 000 combinaisons possibles (fonctionnellement distinctes), en supposant que toutes les fonctions sont utilisées.

Si vous avez moins de 16 fonctions à votre disposition, certains des emplacements resteront vides. Cependant, notez que vous ne pouvez pas placer une fonction dans un emplacement de mise à niveau si l'emplacement actif parent est vide.

Le défi

Vous devez déterminer le nombre de configurations possibles en fonction du nombre de fonctions dont vous disposez. De plus, je généraliserai légèrement le problème en rendant le nombre d'emplacements variable, afin d'éviter des solutions triviales de codage en dur.

Écrivez un programme ou une fonction qui, étant donné deux entiers positifs M ≥ 1et 1 ≤ N ≤ 4M, détermine le nombre d'ensembles de compétences possibles (fonctionnellement distincts) en supposant que Ndes fonctions exactement différentes sont utilisées pour remplir le plus possible d' emplacements Mpassifs, Mactifs et de 2Mmise à niveau.

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

Votre code doit être capable de gérer n'importe quelle entrée jusqu'à et y compris M = 8dans une minute sur une machine de bureau raisonnable. Il y a une certaine marge de manœuvre dans ce domaine, mais cela devrait exclure les solutions de force brute. En principe, il ne devrait pas être difficile de résoudre l'une de ces entrées en moins d'une seconde.

C'est le golf de code, la réponse la plus courte (en octets) l'emporte.

Cas de test

Chaque cas de test est dans le formulaire 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

Ce sont toutes les entrées que votre code doit gérer en une minute (chacune), mais cela devrait en principe fonctionner pour les entrées plus importantes. Vous pouvez utiliser certains des M = 10cas de test suivants pour vérifier 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 octets)

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

Démo en ligne

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$

Ainsi, pour chaque partition, le nombre de distributions de fonctions est

Le code ci-dessus calcule les partitions en utilisant la même approche que Dennis (c'est évident et court, bien que pas très évolutif), puis traite chaque partition en un tableau similaire à celui [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]sur lequel elle peut lever la fonction factorielle puis replier la division.

CJam, 74 67 octets

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

J'ai vérifié tous les cas de test sur mon ordinateur de bureau à l'aide de l' interpréteur Java . Cela a pris 2,2 secondes pour 1 ≤ M ≤ 8 et 3,5 minutes pour M = 10 .

Essayer ce violon dans l'interpréteur CJam ou vérifiez les 84 premiers cas de test à la fois .

Idée

En principe, nous pouvons remplir chaque emplacement actif et ses emplacements de mise à niveau correspondants avec 0 , 1 , 2 ou 3 fonctions. Pour 4M emplacements au total, nous prenons tous les vecteurs V de {0, 1, 2, 3} ^M et filtrons ceux pour lesquels sum (V)> N (plus de fonctions dans les slots non passifs que le nombre total de fonctions disponibles) ou sum ( V) + M <N (pas assez d'emplacements passifs pour les fonctions non actives). Nous trions et dédupliquons tous les vecteurs conservés, car l'ordre des familles de slots n'est pas important.

Avec N fonctions et V = (x ₁ ,…, x _M ) fonctions dans les parties non passives des familles de créneaux, nous calculons le nombre de combinaisons comme suit:

1. Si x ₁ = 0 , il n'y a qu'une seule possibilité pour cette famille d'emplacements.

   Si x ₁ = 1 , il y a N possibilités, puisque nous avons N fonctions, et la fonction doit aller dans l'emplacement actif.

   Si x ₁ = 2 , nous devons placer une fonction dans l'emplacement actif et une autre dans un emplacement de mise à niveau (peu importe lequel). Il y a N choix pour l'emplacement actif et N-1 choix restants pour l'emplacement de mise à niveau, donnant un total de N (N-1) combinaisons.

   Si x ₁ = 3 , il y a N choix pour l'emplacement actif, N - 1 choix restants pour le premier emplacement de mise à niveau et N - 2 pour le deuxième emplacement de mise à niveau. Étant donné que les emplacements de mise à niveau n'ont pas d'ordre, cela compte chaque combinaison deux fois, il y a donc N (N - 1) (N - 2) combinaisons uniques.

   En tout cas, il y en a N! / ((N - x ₁ )! × (x ₁ - 1)! Combinaisons pour cette famille.

2. Nous avons utilisé x ₁ fonctions, donc définissez N: = N - x ₁ et répétez l'étape 1 pour x ₂ , puis x ₃ , etc.

3. Si V contient des doublons, le produit des résultats ci-dessus aura compté toutes les combinaisons plusieurs fois. Pour chaque élément unique de V , s'il apparaît r fois dans V , il y a r! façons équivalentes d'organiser ces familles d'emplacements, donc le résultat ci-dessus doit être divisé par r! .

4. Le résultat final est le nombre de combinaisons uniques pour que V .

Pour calculer le nombre total de combinaisons uniques, tout ce qui reste à faire est de calculer la somme des résultats pour chaque V .

Code

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.