Problema E : Eleven
La redacción del problema es muy simple, aun que el problema no lo es, lo que dice el problema que dado un número N hay que encontrar todos los anagramas de N (que no tengan dígitos ceros a la izquierda) , tal que sean divisibles por 11, la solución de programación dinamica se ve obvia, pero la forma de hacerla no lo es, un comentario de Ulises Méndez sobre la propiedad del 11 me ayudo a ver una solución no tan complicada, si buscan en internet encontraran que para que un numero sea divisible por 11 basta con sumar los dígitos que están en posiciones pares y resta le todos los dígitos que están en posiciones impares, si el resultado es divisible por 11 entonces el numero de divisible por 11.
Por ejemplo: 4785 , sumamos las posiciones impares 4 + 8 = 12 y luego sumamos las posición pares 7 + 5 = 12, restamos el segundo al primero 12 - 12 = 0 , y como 0 % 11 = 0, por tanto es divisible por 11.
Ya que tenemos este concepto solo nos tenemos que preocupar que la diferencia entre los pares eh impares sea divisible entre 11. Existe otro detalle, ya que nos piden que los anagramas sean numero sin ceros a la izquierda, esto es sencillo ( aun que no trivial de ver) , nosotros forzamos al numero que vamos a generar a que su primer dígito sea diferente de cero, es por eso que van a ver en el codigo esta parte ( countDigit es una arreglo donde guardamos el numero de 0, 1, 2 , 3, .. 9 que hay en el numero que leemos al inicio)
for( digit = 1; digit <= 9; digit++)
if( countDigits[ digit ] > 0 ){
countDigits[ digit ]--;
memset( vis, 0, sizeof( vis ));
res = ( res + solve( 0 , pares, impares - 1, 11 - digit)) % MOD;
countDigits[ digit ]++;
}
Como ven descartamos un dígito el 1 o el 2, o el 3, ... al 9, dependiendo cual tratamos de forzar a que sea el primer digito de nuestro posible anagrama. Posteriormente resolvemos nuestra dinamica mandando ( digitoInicial ( siempre se empieza en cero para recorrer de cero a nueve), Numero de elementos pares que nos faltan, numero de elementos impares ( como ven se resta el primero que ya utilizamos) , modulo que llevamos hasta el momento (como ven es 11 - digito, ya que los impares se restan ).
La dinamica es de la siguiente forma:
solve( int posDigit, int pares, int impares, int mod)
Nosotros nos vamos a estar moviendo de dígito en dígito, primero en el cero, luego en el uno,... , hasta el nueve, para eso es posDigit también llevamos el número de elementos pares que nos hace falta colocar en nuestro anagrama factible, así como los impares , el mod solo contendrá la suma de las diferencia de los dígitos pares e impares.
Lo siguiente para resolver el problema es darse cuenta que si tenemos 5 dígitos de un tipo, solo los podemos colocar de la siguiente manera, { (0 pares , 5 impares), ( 1 par, 4 impares), ( 2 pares, 3 impares), ( 3 pares, 2 impares), ( 4 pares, 1 impar) , ( 5 pares, 0 , impares) }, no son muchas en el peor de los casos vamos a tener 100 dígitos iguales, en esta parte hago uso de un for con la variable slice esta variable va a cortar y determinar cuantos impares y pares:
for( slice = 0; slice <= countDigits[ posDigit ]; slice++){
Dependiendo del numero de elementos del dígito vamos a partilos como se los había mencionado , el numero de pares seria igual a slice y numero de impares seria igual a countDigits[ posDigit ] - slice , agregando estos dígitos tenemos que calcular nuestro nuevo modulo, ya que al agregar digitos pares e impares se modifica:
newmod = ((mod + ( slice * posDigit ) - ( (countDigits[ posDigit ] - slice ) * posDigit )) % 11 + 11 ) % 11
Se suma el modulo que tenemos y se agregan los dígitos pares e impares, pueden notar que se restan los impares, también van a ver varios módulos 11, esto es por que la resta puede quedar un numero negativo y debemos asegurarnos que sea siempre positivo.
Ya que tenemos nuestro nuevo modulo podemos contar cuantos resultados tenemos si escogemos esa cantidad de pares eh impares con el digito en cuestión, lo que hacemos es invocar el solve para que calcula el siguiente dígito posDigit + 1 , también hay que restar nuestros pares usados en este momento, así como los impares y lo invocamos con nuestro nuevo modulo.
R = solve( posDigit + 1, pares - slice, impares - ( countDigits[ posDigit ] - slice ) , newmod ) % MOD;
Todavía no se acaba, ya colocamos el numero de dígtos pares, pero en el numero pueden estar distribuidos en cualquier posición disponible para dígitos pares, es por eso que se hacen las combinaciones de numeroParesDisponibles en paresAAgregar, lo mismo para los impares y estos dos resultados se multiplican el numero de soluciones factibles que obtuvimos del proximo digito.
R = ( R * ( ( comb(pares, slice) * comb( impares, ( countDigits[ posDigit ] - slice ) )) % MOD) ) % MOD;
( si es complejo de enterder pero espero les sirva el post, si tienen dudas o quieren que aclare algo mas, no duden en solicitarlo a rodrigo.burgos@gmail.com).
Aquí les dejo el código completo para que lo analicen:
/* Rodrigo Burgos Dominguez */
# include "stdio.h"
# include "string.h"
# define MOD ((long long)1000000007)
char num[200];
int length, countDigits[10];
long long dinComb[102][102];
long long din[11][102][102][12];
int vis[11][102][102][12];
long long comb(int a, int b){
if( a == 0 && b == 0 ) return 1;
if( b > a ) return 0;
if( b == 0 ) return 1;
if( b < 0 ) return 0;
if( dinComb[a][b] != -1 ) return dinComb[a][b];
return dinComb[a][b] = (comb(a - 1, b - 1) + comb(a - 1, b)) % MOD;
}
long long solve( int posDigit, int pares, int impares, int mod){
long long res = 0, R;
int newmod, slice;
if( pares < 0 || impares < 0 ) return 0;
if( posDigit == 10 ) {
return (pares == 0 && impares == 0 && mod == 0) ? 1 : 0 ;
}
if( vis[posDigit][pares][impares][mod] == 1) return din[posDigit][pares][impares][mod];
vis[posDigit][pares][impares][mod] = 1;
for( slice = 0; slice <= countDigits[ posDigit ]; slice++){
newmod = ((mod + ( slice * posDigit ) - ( (countDigits[ posDigit ] - slice ) * posDigit )) % 11 + 11 ) % 11;
R = solve( posDigit + 1, pares - slice, impares - ( countDigits[ posDigit ] - slice ) , newmod ) % MOD;
R = ( R * ( ( comb(pares, slice) * comb( impares, ( countDigits[ posDigit ] - slice ) )) % MOD) ) % MOD;
res = (res + R) % MOD;
}
return din[posDigit][pares][impares][mod] = res % MOD;
}
main(){
int pares, impares, digit, x;
long long res;
memset( dinComb, -1, sizeof( dinComb ) );
while( scanf("%s", num) != EOF ){
length = strlen( num );
memset( countDigits, 0, sizeof( countDigits ));
for( x = 0 ; x < length ; x++) countDigits[ num[x] - '0']++;
pares = ( length / 2 );
impares = ( length / 2) + ( length % 2);
res = 0;
for( digit = 1; digit <= 9; digit++)
if( countDigits[ digit ] > 0 ){
countDigits[ digit ]--;
memset( vis, 0, sizeof( vis ));
res = ( res + solve( 0 , pares, impares - 1, 11 - digit)) % MOD;
countDigits[ digit ]++;
}
printf("%lld\n", res);
}
return 0;
}
