Nombre de multisets de sorte que chaque nombre de 1 à

Mon problème. Compte tenu de , je veux compter le nombre de multijeux valide S . Un multiset S est valide si$n$$S$$S$

• La somme des éléments de est n , et$S$$n$
• Chaque numéro de à n peut être exprimée de manière unique comme une somme de quelques - uns des éléments de S .$1$$n$$S$

Exemple. Par exemple , si alors { 1 , 1 , 1 , 1 , 1 } , { 1 , 2 , 2 } , { 1 , 1 , 3 } sont valides.$n=5$$\{1,1,1,1,1\}, \{1,2,2\}, \{1,1,3\}$

Cependant, n'est pas valide car 2 peut être formé à la fois par { 1 , 1 } et { 2 } (c'est-à-dire que 2 peut être exprimé comme 2 = 1 + 1 et 2 = 2 ) , donc la deuxième condition ne tient pas. De même 3 peut être formé par { 2 , 1 } et { 1 , 1 , 1 } .$S=\{1,1,1,2\}$$\{1,1\}$$\{2\}$$2=1+1$$2=2$$\{2,1\}$$\{1,1,1\}$

} est également invalide car tous les nombres de 1 à 5 peuvent être créés de manière unique, mais la somme des éléments de S n'est pas 5 .$S=\{1,2,4$$1$$5$$S$$5$

J'ai essayé de trouver un bon algorithme pour ce problème depuis un certain temps, mais je ne peux pas le résoudre. C'est du codechef . J'ai vu certaines des solutions soumises, mais je n'ai toujours pas pu obtenir la logique pour résoudre le problème. REMARQUE: la limite de temps pour la question est de 10 secondes et $n<10^9$

Pour un multiset j'utiliserai la notation a i$S = \{(a_1, c_1), (a_2, c_2) ... \}$ si i < j , ce qui signifie qu'un i se produit c i fois en multiset S.$a_i<a_j$$i<j$$a_i$$c_i$

Jusqu'à présent, j'ai tiré quelques conclusions

• Le premier élément du multiset trié requis doit être $1$
• Soit soit un ensemble suivant les deux propriétés alors ∀ r < k a r + 1 = a r  ou  $S=\{1,a_2 \cdots a_k\} | a_1 \leq a_2\cdots \leq a_k$$\forall r<k \ \ a_{r+1} = a_r \text{ or } (\sum_{i=0}^ra_i) + 1$
• Soit , où a $S=\{(1,c_1),(a_2,c_2) \cdots (a_k,c_k)\} | a_1 \leq a_2\cdots \leq a_k$$a_i$ se produit fois, suit les propriétés requises, puis de la conclusion ci-dessus nous pouvons dire que ∀ i a i | n + 1 et$c_i$$\forall i \ a_i|n+1$ si j > i . Preuve: a i + 1 = ( a i c i + a i - 1 ) + 1 ⇒ a i | a i + $a_i | a_j$$j > i$
  $a_{i+1} = (a_ic_i + a_i -1 ) + 1 \Rightarrow a_i | a_{i+1}$
• Considérons maintenant c'est-à-dire tous les les nombres suivants après 1 seront un multiple de d . Soit donc f ( n $S=\{ \underbrace{1,1 \cdots 1}_{d-1},d,d \cdots d,dm_1, dm_1 \cdots dm_1,dm_2, dm_2 \cdots dm_2, \cdots \}$$d$$f(n)$être le compte d'un tel multiset possible alors où je suis sommant sur tout nombre possible de1's(=d-1). En d'autres termes,f(n-1)=g(n)$f(n) = \sum_{d|n+1, d\neq 1} f(\frac{n-(d-1)}{d})$$1's$$=d-1$$f(n-1)=g(n)=\sum_{d|n,d \neq n}g(d)$

Enfin mon problème est réduit à ceci - trouver d'une manière efficace afin qu'il ne dépasse pas la limite de temps.$g(n)$

Voici ce que fait la solution la plus rapide . C'est en effet calculer votre fonction Étant donné n , nous le factorisons (voir ci-dessous), puis calculons tous les facteurs (voir ci-dessous) f 1 , … , f m dans un ordre tel que f i | f j implique i ≤ j (propriété P). Nous calculons maintenant g selon la formule en passant en revue les facteurs dans l'ordre donné. La propriété P garantit que lorsque nous calculons g ( d ) , nous avons déjà calculé g ( e ) pour tous les facteurs non triviaux

Plus en détail, nous passons en revue les facteurs dans l'ordre, et pour chaque facteur , nous trouvons tous ses facteurs non triviaux en vérifiant lequel de f 1 , … , f i - 1 divise f i .$f_i$$f_1,\ldots,f_{i-1}$$f_i$

Affacturage: prétraitement: nous faisons une liste de tous les nombres premiers inférieurs à utilisant le tamis Eratosthène. Étant donné n , nous utilisons simplement la division d'essai.$10^9$$n$

Générer tous les facteurs: cela se fait de manière récursive. Supposons que . Nous exécutons t boucles imbriquées l 1 ∈ { 0 , … , k 1 } , … , l t ∈ { 0 , … , k t } , et sortons p l 1 1 ⋯ p l $n = p_1^{k_1} \cdots p_t^{k_t}$$t$$l_1 \in \{0,\ldots,k_1\},\ldots,l_t \in \{0,\ldots,k_t\}$ . Vous pouvez prouver la propriété P par induction.$p_1^{l_1}\cdots p_t^{l_t}$

Optimisation: le programme étant exécuté sur plusieurs entrées, nous pouvons utiliser la mémorisation pour gagner du temps sur différentes entrées. Nous ne mémorisons que de petites valeurs (jusqu'à ), ce qui nous permet de stocker toutes les valeurs mémorisées dans un tableau. Le tableau est initialisé avec des zéros, et ainsi nous pouvons dire quelles valeurs sont déjà connues (puisque toutes les valeurs calculées sont positives).$10^5$

Si la factorisation première de est p k 1 1 , … , p k t t , alors f ( n ) ne dépend que de ( k 1 , … , k t ) , et en fait uniquement de la version triée de ce vecteur . Chaque nombre inférieur à 10 9 a au plus 29 facteurs premiers (avec répétition), et puisque p ( 29 ) = 4565 , il semble possible de calculer $n+1$$p_1^{k_1},\ldots,p_t^{k_t}$$f(n)$$(k_1,\ldots,k_t)$$10^9$$29$$p(29)=4565$$f$(ou plutôt ) pour tous, récursivement. Cette solution pourrait être plus rapide s'il y avait de nombreuses entrées différentes; en l'état, il y en a au maximum 10 .$g$$10$

Il est également possible que cette fonction, mappant les partitions au correspondant , ait une forme analytique explicite. Par exemple, g ( p k ) = 2 k - 1 , g ( p 1 … p t ) est donné par A000670 , et g ( p 2 1 p 2 … p t ) est donné par A005649 ou$g$$g(p^k) = 2^{k-1}$$g(p_1\ldots p_t)$$g(p_1^2 p_2\ldots p_t)$ A172109 .

OK, vous avez donc une relation de récurrence pour (voir la fin de votre question).$g(\cdot)$

À ce stade, il semble qu'une approche naturelle serait d'écrire l'algorithme récursif pour calculer et d'appliquer la mémorisation afin de ne pas calculer g ( i ) plus d'une fois. En d'autres termes, lorsque vous calculez g ( i ) , vous le stockez dans une table de hachage qui mappe i ↦ g ( i ) ; si vous avez besoin de connaître g ( i $g(n)$$g(i)$$g(i)$$i \mapsto g(i)$$g(i)$ à l'avenir, vous pouvez le rechercher dans la table de hachage.

$n$$n$$n\le 10^9$ .

$g(1),g(2),g(3),g(4),g(5),\ldots$

Voici un indice pour vous aider à démarrer. Appliquer des algorithmes de programmation dynamique standard pour énumérer l'ensemble des partitions d'un entier et ajouter une logique pour vérifier laquelle permet une modification unique en vérifiant de manière itérative toutes les sommes, en effectuant des modifications et en vérifiant l'unicité.

$S$$i$$1 \le i \le n$$S$$i$

$S$$n$$S$ (la condition unique de changement)? Cela devrait être assez facile, si vous avez résolu le précédent.

$P(n)$$P(1), P(2), \dots, P(n)$$P(n+1)$

Voici une approche qui sera probablement meilleure.

$S$$n$$T$$S$$T$$n'$

$x$$S$$S$$T$$x$$S$$S$$T$$n$

$S$$A[1\ldots |S|,1 \ldots n]$$A[i,j]$$j$$i$$S$$i$$S$$S$$S=\{s_1,s_2,\dots,s_k\}$$s_1\le s_2 \le \cdots \le s_k$$A[i,j]$$A[1\ldots i-1, 1\ldots j-1]$$A[i,j] = A[i-1,j] \lor A[i-1,j-s_i]$$j>s_i$$A[i,j]=A[i-1,j]$$S$

$T$$S$$S$$T$$n$$S$$n'$$T$$n+1,n+2,\ldots,n'$$T$$A$$A[1\ldots |T|, 1 \ldots n']$$A[|T|,n+1], A[|T|,n+2], \ldots, A[|T|,n']$$T$$S$

$S$$n$$n\le 20$$P[1\ldots 20]$$P[5]$$S$$P[n]$$S$$n$

$P[n]$$P[1]$$\{1\}$$n$$S \in P[n]$$T$$S$$n'$$T$$T$$P[n']$$n' \le 20$

Cela devrait être assez faisable. Bonne chance! S'amuser! Travailler à travers les détails sera un bon exercice d'apprentissage en programmation dynamique.