Freut mich, dich kennenzulernen. Ich bin ein Anfänger, der letzte Woche angefangen hat, an Wettkampfprofis zu arbeiten.
Gestern gab es einen Wettbewerb namens Atcoder Grand Contest, der einer der schwierigsten Atcoder ist, und ich habe zum ersten Mal teilgenommen.
Der gestrige war der schwierigste und je nach Geschwindigkeit reichte es aus, um eine orangefarbene Leistung mit zwei Platzierungen zu erzielen. Ich konnte nur eine Frage lösen, war aber auch überrascht über die Schwierigkeit der ersten Frage (zu verschieden von ABC).
Als ich die Erklärung von 2. Frage las, kam der Satz ** Lucas 'Satz ** heraus. (Wenn Sie interessiert sind, lesen Sie bitte auch die Problemstellung) Ich war überrascht, es so zu sehen, als wäre es gesunder Menschenverstand lol
Als ich mit * "Lucas 'Theorem Competition Pro" * gegoogelt habe, habe ich es getroffen, also dachte ich, es sollte in Erinnerung bleiben, und ich habe beschlossen, es bis jetzt zu erklären und umzusetzen. (Implementiert von Python)
ps.) Ist es ein allgemeiner Satz im professionellen Bereich des Wettbewerbs? Ich würde es begrüßen, wenn Sie es mir sagen könnten.
p: Primzahl m, n: nicht negative ganze Zahl C (n, k): = (Zahl, wenn k aus n ausgewählt ist) Wann
C(m,n) \equiv \prod_{i=0}^l C(m_i, n_i) \ \ \ \ (mod\ p) \\
Jedoch,
m_lm_{l−1}⋯m_1m_0 := (p-ary Anzeige von m)\\
n_ln_{l−1}⋯n_1n_0 := (n p-ary Anzeige)
Und.
Wenn ich es auf meine eigene Weise zusammenfasse ** "Satz, den man genießen muss, wenn man den Rest von C (n, k) findet" ** Ich habe es so interpretiert.
Der Satz von Lucas wird verwendet, um die Informationen in diesem Wettbewerb zu finden, was die Gleichmäßigkeit von C (n, k) für alle eingegebenen Zahlen erfordert. (P = 2)
Wenn zum Beispiel die Gleichmäßigkeit von C (7,2) gefunden wird, (n = 5, k = 2)
7\ → 111\\
2\ → 010
Konvertieren Sie dann zuerst n und k in binär Finden Sie C (n, k) für jede Ziffer und multiplizieren Sie mit dem gefundenen C (n, k).
C(1,0)*C(1,1)*C(1,0) = 1*1*1 = 1
Daher kann der Rest der Division von C (7,2) durch 2 als 1 abgeleitet werden, und es ist ersichtlich, dass es sich um eine ungerade Zahl handelt.
Die Implementierung selbst ist nicht so schwierig, aber es ist mühsam, sie während des Wettbewerbs durchzuführen. Deshalb habe ich sie implementiert, damit sie in Zukunft verwendet werden kann. (Bitte weisen Sie auf Fehler hin)
from scipy.special import comb
#Eine Funktion, die x in n-fache Notation konvertiert
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)Eine Funktion, die den Rest der Division durch p zurückgibt
def lucas(n, k, p):
#Notation von n und k in p-arischer Notation
n_p = n_ary(n, p)
k_p = n_ary(k, p)
# n_p und k_Richten Sie die Ziffern von p aus(Füllen Sie die linke Seite mit 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
Als ich den Wettbewerb beendete und die Antwort sah, fühlte ich "Ich kann nicht daran denken." Als ich mir danach das Kommentarvideo ansah,
――Wenn Sie es bis zu einem gewissen Grad tun, wissen Sie es ~ ――Es ist eine übliche Methode ~
Der Kommentator sagte einen Satz wie diesen und ich wurde über meinen Mangel an Wissen informiert. Es mag ein Problem mit der Macht von Hirameki geben, aber vorher wurde mir klar, dass mir Wissen fehlte, und ich beschloss, mir Sorgen um Hirameki zu machen, nachdem ich das Wissen hatte. (In diesem Fall musste ich mir Pascals dreieckiges Ding als Binomialkoeffizientenverschränkung vorstellen.)
Beim nächsten großen Wettbewerb werde ich mein Wissen vertiefen, damit ich 2 abschließen kann.