Distances entre Maisons

[FLBP]

C'est plus un énigme qui tient de la complexité algorithmique en temps, donc touche plus le côté informatique, mais qui fait appel aussi aux maths, donc je l'ai posté ici:
Soit une chaîne de longueur N faite de "M", une maison et de '.', une route: M.MM..M
Donner le nombre de maisons étant séparées d'un espace [0,1,2,...,N-1], sachant qu'un maison est elle-même séparée par un distance de 0.
Ici dans l'exemple cela serait A de d = [4,1,1,2,1,0,1]
N peut prendre des valeurs très élevées.
Trouver un algorithme ou une méthodologie permettant de trouve A en O(N log(N))
Bonne chance

[Ben314]

Salut,
J'ai l'impression que ça marche avec des séries de Fourrier discrètes :
On considère la suite où selon qu'il y a une maison ou pas à la position qu'on complète en posant .
Ce qu'on veut calculer, c'est, la suite où, pour tout , on a

Si on calcule la transformée discrète de la suite , c'est à dire les coefficients tels que avec alors on a donc pour retrouver les , il suffit de faire la transformée de Fourrier de la suite des

Et comme on sait depuis Gauss qu'une transformée de Fourrier discrète peut se faire en un temps O(N.ln(N)), ça doit faire le compte.

[FLBP]

C'est la réponse que j'attendais, Bravo !
Je l'avais fait de la même manière mais en exprimant la suite de maison par un polynôme, que je multipliais après un transformée de Fourier, par la série des inverses (enfin je me comprend). Et avec une FFT on arrive à O(Nlog(N)) !
Bref Bravo.