Dans beaucoup d'applications internet, on veut qu'un programme situé sur un serveur distant s'exécute sur les données que lui envoie un utilisateur depuis son navigateur web, et, une fois l'exécution terminée, qu'il renvoie le résultat au navigateur. Entre le navigateur web du client et le serveur web sur lequel l'application est basée, la communication est relativement restreinte : comme elle se base sur divers protocoles, elle ne doit en particulier pas utiliser les caractères spéciaux réservés par ces protocoles. Ainsi, on ne peut par exemple pas envoyer directement des entiers en représentation binaire : à la place, on envoie généralement leur représentation sous forme de chaîne de caractères.
D'autre part, dans les domaines dans lesquels on doit manipuler de manière exacte de très grands entiers (par exemple en cryptographie), il n'est pas non-plus possible d'utiliser la représentation de base des entiers, qui est limitée aux entiers jusqu'à 2^32-1 ou 2^64-1 en général. Typiquement, la multiplication de deux très grands entiers doit être décomposée en opérations sur des entiers plus petits.
Énoncé
Dans cet exercice, on va manipuler des entiers trop grands pour qu'on utilise le type entier de base. Plus précisemment, on va calculer l'image par un polynôme P d'un grand entier n. Les coefficients du polynôme ne pourront valoir que 0 ou 1, ainsi on pourra le décrire par la liste des indices de ses coefficients valant 1 (le polynôme "1+x+x^3" sera donc représenté par la liste "0 1 3", par ordre croissant d'indices). Les indices descriptifs des polynomes seront toujours suffisamment petits pour pouvoir être représenté en mémoire par un entier de base (type int/integer). L'entier x sera donné, comme d'habitude, par la chaîne de caractères de sa représentation (en base 10), mais cette fois, on ne pourra pas directement la convertir en un entier du langage. Pour le polynôme "1+x+x^3", si on donne x=5, il faudra donc rendre 1+5+5^3 = 1+5+125 = 131.
Étant donnés P et x, calculer P(x).
Entrée
L'entrée se décompose en deux lignes :
la liste des indices (entiers de base) des coefficients de P valant 1, séparés par des espaces,
le grand entier x (suivi d'un retour à la ligne).
Sortie
La sortie est l'image de x par P (la chaîne de caractère de sa représentation en base 10) suivie d'un retour à la ligne.
Chaque test prendra maximum 10 secondes.