En quoi l’approche pour résoudre Google APAC rond B problème?

J’ai vu peu de solutions et qu’ils utilisent après la relation :
f (m, n) = (f (m - 1, n - 1) * m) % MOD + (f (m, n - 1) * (M - m)) % MOD

Comment rejoindre cette équation?

Réponse

En fait, la récidive est
f (m, n) = (f (m, n - 1) * m) % MOD + (f (m-1, n - 1) * (M - (m-1))) % MOD

f = le nombre de manières dont nous pouvons obtenir une chaîne de longueur n où m personnages différents ont été utilisés au moins une fois

Disons que nous avons une chaîne S de longueur (n-1).

1. si en S, m personnages différents ont été utilisés au moins une fois, nous pouvons étendre cette chaîne à la longueur (n) en ajoutant un de ces personnages de m .
Plusieurs façons de le faire est, m*f(m,n-1).

2. Si, en S, m-1 personnages différents ont été utilisés au moins une fois, puis nous pouvons l’étendre à une chaîne de longueur (n) en choisissant les caractères M-(m-1) qui n’ont pas été utilisés avant.
Plusieurs façons de le faire est, (M-(m-1))*f(m-1,n-1).


Tags: Algorithmes, Google, Résolution de problèmes, Question How-to, Google Apac 2015