Dado un número N <10 ^ 100, ¿cuántos números cuyos dígitos son una permutación de dígitos en N que son divisibles por 11? Gracias por adelantado.

Answer 1

Durante el concurso, resolví el problema usando programación dinámica.

Primero, veamos la prueba de divisibilidad para 11. Un número es divisible por 11 si la suma de dígitos en posiciones impares y la suma de dígitos en posiciones pares difiere en un múltiplo de 11. Entonces, lo que debemos hacer es encontrar la cantidad de formas de dividir los dígitos del número original en dos partes de igual tamaño (o que difieran en una si la longitud original es impar) y permutando cada parte de tal manera que sus sumas difieran en un múltiplo de 11.

Para resolver esto usando programación dinámica, definamos primero algunas cantidades:

• L es la longitud del número original
• M es el número de dígitos en posiciones impares en el número. Si L es par, M = L / 2. De lo contrario M = (L + 1) / 2
• cnt [d] es el número de veces que el dígito d (0≤d≤9) aparece en el número original
• csum [d] es la suma de cnt [i] para d≤i≤9.
• DP [i] [j] [k] es el número de formas de formar dos cadenas usando los dígitos de i a 9, de modo que la primera cadena tiene j dígitos (y la segunda tiene csum [i] -j dígitos) y la diferencia entre las sumas de dígitos en las dos mitades deja el resto k en la división por 11.

Ahora, es fácil ver que DP [0] [M] [0] da la respuesta requerida. El caso base para nuestra recurrencia sería DP [10] [0] [0] = 1 y DP [10] [*] [*] = 0 de lo contrario. Veamos ahora la recurrencia exacta.

Supongamos que hemos encontrado DP [i + 1] [*] [*]. ¿Cómo calculamos DP [i] [j] [k]? La primera cadena puede tener entre 0 y min (j, cnt [i]) ocurrencias del dígito i. Deje que el número exacto de ocurrencias sea p. Luego, al incluir el dígito i, se agrega p * i a la suma de dígitos en la primera mitad, y (cnt [i] -p) * i a la suma de dígitos en la segunda mitad. El recordatorio de la diferencia ha sido cambiado por q = (2 * p-cnt [i]) * i% 11. Deje j ‘= jp y k’ = kq. Antes de agregar todos los dígitos i, deberíamos haber estado en el estado DP [i + 1] [j ‘] [k’]. Dado que hay formas C (j, p) de colocar los pi en la primera cadena y formas C (csum [i] -j, cnt [i] -p) de colocar las i en la segunda cadena, la contribución a DP [i] [j] [k] es C (j, p) * C (csum [i] -j, cnt [i] -p) * DP [i + 1] [j ‘] [k’]. Resumiendo esto para todos los valores de p nos da DP [i] [j] [k].

Aquí está el pseudocódigo:

  DP [11] [M + 1] [11] // Inicializado a 0
 DP [10] [0] [0] = 1

 para i = 9 a 0:
   para j = 0 a M:
     para k = 0 a 10:
       para p = 0 a min (j, cnt [i]):
         j '= jp
         k '= (ki * (2p-cnt [i]))% 11
         if (i> 0) DP [i] [j] [k] + = C (j, p) * C (csum [i] -j, cnt [i] -p) * DP [i + 1] [j '] [k']
         más DP [i] [j] [k] + = C (j-1, p) * C (csum [i] -j, cnt [i] -p) * DP [i + 1] [j '] [ k ']
       fin
     fin
   fin
 fin

 devolver DP [0] [M] [0]

La condición if hace el trabajo de evitar los ceros iniciales al restringir los ceros para que se coloquen solo en las posiciones restantes. En general, el ciclo se ejecuta menos de 100 * 50 * 11 veces, asegurando que la solución se termine dentro del límite de tiempo.

Answer 2

Esta no es una respuesta completa, solo señala algunas condiciones obvias en la respuesta completa.

Una prueba de divisibilidad es sumar dígitos alternos del número (base 10 [2 × 5 :-)]) y si estas dos sumas s_even y s_odd difieren en un múltiplo de once, el número original era divisible por once.

Por lo tanto, un número que consiste solo en una repetición impar de un solo dígito no puede tener permutación con la propiedad deseada. (111, 22222, 6, 55, …)
Suponiendo que se nos permite hacer uso del mar infinito de ceros a la izquierda, podemos generalizar para hacer dos sumas parciales, una de cualquier subconjunto de dígitos y la otra los dígitos restantes. Si la diferencia entre estas sumas es un múltiplo de once, entonces tenemos una solución.

224 => 242 = 11 * 22
2278 => 2728 = 11 * 248

Si la pregunta carecía de la restricción que limita N a menos de 10 ^ 100, entonces por cada permutación que funcionó multiplicándola por 10 produciría otra (o inyectando 2 ceros consecutivos en cualquier lugar dentro del número). Esto daría un recuento infinito para un número, cero para otros.

Como sabemos que hay números t = floor (10 ^ 100/11) que son divisibles por 11, podemos “simplemente” etiquetar cada uno de ellos con la lista del recuento de cuántos 1’s, 2’s, 3’s, … 9’s compuestos el número. Contando el número con cada total de etiquetas a t.
Las etiquetas están limitadas a que la suma sobre la etiqueta sea menor o igual a 100.