Contar secuencias no decrecientes de una longitud dada N hechas de múltiplos bajo un límite M

Question

Dados los números enteros N y M, ¿cuántas secuencias A de N enteros satisfacen las siguientes condiciones?

$1 A_i M(i=1,2,…,N)$

$A_{i+1}$ es un múltiplo de $A_i$ . $(i=1,2,…,N1)$

Por ejemplo, para N=3 y M=4, estas son las secuencias: $(1,1,1), (1,1,2), (1,2,2), (2,2,2), (1,1,3), (1,3,3), (3,3,3), (1,4,4), (2,4,4), (4,4,4), (2,2,4), (1,2,4), (1,1,4) $ Por lo tanto, la respuesta es 13

Como se trata de un problema en el que no espero encontrar una forma cerrada, todas las respuestas computacionales son bienvenidas, pero las más eficientes son más apreciadas. Mi corazonada dice que podemos calcular en algo como $O(N\ log M)$ o $O(M\ log N)$ tiempo.

Answer 1

Este es un enfoque de programación dinámica.

Dejemos que $f(N,M)$ sea la respuesta. Yo reclamo $f(N,M)=\sum\limits_{j\ge 1} f(N-1, \lfloor \frac Mj \rfloor)$ . Para ver esto, si $A_1$ es conocida, la secuencia $(\frac{A_2}{A_1}, \cdots, \frac{A_N}{A_1})$ es una secuencia que satisface las condiciones de $(N-1, \lfloor \frac{A_N}{M} \rfloor)$

¿Cuántos valores distintos para $\lfloor \frac Mj \rfloor$ ¿existe? Aproximadamente $2\sqrt{M}$ . Nota $\lfloor \frac Mj \rfloor$ es distinto para $j<\sqrt{M}$ y podemos contar el número de soluciones de $\lfloor \frac Mj\rfloor=k$ en $O(1)$ ya que esto es simplemente $\lfloor \frac {M}{k} \rfloor - \lfloor \frac {M}{k+1} \rfloor$

Este es un $O(NM^{1.5})$ enfoque. Me pregunto si hay un enfoque más rápido.