Contexte

Ravi de vous rencontrer. Je suis un débutant qui a commencé à travailler sur des professionnels de la compétition la semaine dernière.

Hier, il y avait un concours appelé Atcoder Grand Contest, qui est l'un des Atcoders les plus difficiles, et j'y ai participé pour la première fois.

Celui d'hier était le plus difficile, et selon la vitesse, il suffisait d'obtenir une performance orange avec 2 arrivées. Je n'ai pu résoudre qu'une seule question, mais j'ai également été surpris de la difficulté de la première question (trop différente de ABC)

Quand j'ai lu l'explication de 2e question, le théorème ** théorème de Lucas ** est sorti. (Si vous êtes intéressé, veuillez également lire l'énoncé du problème) J'ai été surpris de le voir comme si c'était du bon sens lol

Quand j'ai googlé avec * "Lucas's Theorem Competition Pro" *, je l'ai frappé, alors j'ai pensé qu'il fallait s'en souvenir, et j'ai décidé de l'expliquer et de l'implémenter. (Implémenté par python)

ps.) Est-ce un théorème courant dans le domaine professionnel de la compétition? Je vous serais reconnaissant si vous pouviez me le dire.

Quel est le théorème de Lucas?

p: nombre premier m, n: entier non négatif C (n, k): = (nombre lorsque k sont sélectionnés parmi n) Quand

  C(m,n) \equiv \prod_{i=0}^l C(m_i, n_i) \ \ \ \  (mod\ p) \\

cependant,

m_lm_{l−1}⋯m_1m_0 := (affichage p-aire de m)\\
n_ln_{l−1}⋯n_1n_0 := (n affichage p-aire)

Et.

Que veux-tu faire après tout

Quand je le résume à ma manière ** "Théorème à apprécier lors de la recherche du reste de C (n, k)" ** Je l'ai interprété comme ça.

Exemple dans ce cas

Le théorème de Lucas est utilisé pour trouver les informations dans ce concours, qui nécessite la régularité de C (n, k) pour tous les nombres d'entrée. (P = 2)

Par exemple, lors de la recherche de la régularité de C (7,2), (n = 5, k = 2)

7\ → 111\\
2\ → 010

Commencez par convertir n et k en binaire, puis Trouvez C (n, k) pour chaque chiffre et multipliez par le C trouvé (n, k).

C(1,0)*C(1,1)*C(1,0) = 1*1*1 = 1

Par conséquent, le reste de la division de C (7,2) par 2 peut être dérivé comme 1, et on peut voir que c'est un nombre impair.

la mise en oeuvre

L'implémentation en elle-même n'est pas si difficile, mais c'est gênant de le faire pendant le concours, donc je l'ai implémentée pour qu'elle puisse être utilisée à l'avenir. (Veuillez signaler toute erreur)

from scipy.special import comb

#Une fonction qui convertit x en notation n-aire
def n_ary(x, n):
	nums = '0123456789ABCDEF'
	result = ''
	while(1):
		result = nums[int(x % n)] + result
		x = x // n
		if x==0:
			break
	return result

# C(n,k)Une fonction qui renvoie le reste de la division par p
def lucas(n, k, p):
	#Notation de n et k en notation p-aire
	n_p = n_ary(n, p)
	k_p = n_ary(k, p)
	# n_p et k_Alignez les chiffres de p(Remplissez le côté gauche avec 0)
	k_p = k_p.zfill(len(n_p))

	result = 1
	for n_i, k_i in zip(n_p, k_p):
		result *= comb(int(n_i), int(k_i), exact=True)
	return result

Résumé

Quand j'ai terminé le concours et vu la réponse, j'ai senti "je ne peux pas y penser." Cependant, lorsque j'ai regardé la vidéo du commentaire après cela,

――Si vous le faites dans une certaine mesure, vous le savez ~ ――C'est une méthode courante ~

Le commentateur disait une phrase comme celle-ci, et j'ai été informé de mon manque de connaissances. Il y a peut-être un problème avec le pouvoir d'Hirameki, mais avant cela, j'ai réalisé que je manquais de connaissances, alors j'ai décidé de m'inquiéter pour Hirameki après avoir eu la connaissance. (Dans ce cas, lorsque la chose semblable au triangle de Pascal est sortie, je devais la considérer comme un enchevêtrement de coefficients binomiaux)

Dans le prochain Grand Concours, je renforcerai mes connaissances afin de pouvoir terminer 2.