Es ist ein Kommentar von D-Knight des AtCoder Beginner Contest gestern (16. November 2019). Ich werde hauptsächlich darüber schreiben, wie man $ nCk $ $ \ pmod {10 ^ 9 + 7} $ berechnet.
Die fraglichen $ X $, $ Y $ Einschränkungen, ・ $ 1 \ leqq X \ leqq 10 ^ 6 $ ・ $ 1 \ leqq Y \ leqq 10 ^ 6 $ Daher ist es wichtig zu verstehen, dass DP, BFS und DFS TLE sind. (Alles wird in der Größenordnung von O (NM) sein.)
Wenn der obige Algorithmus nicht funktioniert, muss etwas getan werden, und so kam ich auf die Idee, die in Erläuterung angezeigt wird. Dann müssen Sie nur noch nach $ nCk $ $ \ pmod {10 ^ 9 + 7} $ fragen.
Was wir diesmal finden müssen, ist, dass $ nCk = \ frac {n!} {K! (N-k)!} $ Geteilt durch $ 10 ^ 9 + 7 $.
Es gibt ** 4 ** Punkte (verwirrende Punkte) zu finden, also schauen wir sie uns der Reihe nach an.
Dies ist die Basis der Mod-Berechnung. Dies führt zu einem Überlauf. Nehmen Sie den Rest jedes Mal, wenn Sie stapeln. Im Fall dieser Formel
Ich verstehe, dass ich jedes Mal, wenn ich multipliziere, $ mod $ $ 10 ^ 9 + 7 $ nehme, aber $ \ frac {1} {n-k-1} $ ist eine echte Division. Wie soll ich sie berechnen? Dies ist Kenchons Artikel,
Ist leicht zu verstehen. In ** "3. Teilen von a ÷ b" ** wird ** die Aufteilung der Welt von mod p ** ausführlich beschrieben.
Wenn Sie nur die Schlussfolgerung schreiben, In $ \ mod {p} $ wird die Zahl, die bei Multiplikation mit $ b $ zu $ 1 $ wird, als $ b ^ {-1} $ ausgedrückt. $ a \div b \equiv a \times b^{-1} \pmod{p}$ Es wird sein. Mit anderen Worten, das Finden von $ b ^ {-1} $ (Multiplizieren mit a) ist die Teilung der Mod-Welt. $ b ^ {-1} $ heißt die ** Inverse ** von $ b $ in mod $ p $.
Wie sollen wir dann das umgekehrte Element finden, das in II erschien? Dies ist auch Kenchons Artikel,
Die ausführliche Erklärung ist in geschrieben. Persönlich war die Erklärung von "** 1-5. Eine andere Methode zur Ableitung der inversen graduellen Gleichung **" besonders leicht zu verstehen.
Wenn Sie hier nur die Schlussfolgerung schreiben,
#inv ist 1 ~(b-1)^-Liste mit inversen Werten bis 1
inv[b] = - inv[MOD % b] * (MOD // i) % MOD
Im Implementierungsbeispiel von Kenchon ist es übrigens wie folgt, aber es ist dasselbe, weil es nur MOD auf der rechten Seite hinzufügt, um daraus eine positive Zahl zu machen.
inv[b] = MOD - inv[MOD % b] * (MOD // i) % MOD
Beispiel) ・ $ 3 \ pmod {11} \ equiv 3 + 11 = 14 $ ・ $ -3 \ pmod {11} \ equiv -3 + 11 = 8 $
Wenn Sie das obige I bis III verstehen, wird es ein bisschen mehr sein. Was wir finden wollen, ist $ \ pmod {p} $ in der folgenden Formel, wobei $ p = 10 ^ 9 + 7 $.
Um dies zu finden
(1) Liste der Floor Mods von $ 1 bis n $
[
(2) Originalbodenliste umkehren
[
Wenn Sie es haben, werden Sie es leicht finden.
(1) ist
In Bezug auf (2),
Wenn Sie alle drei haben, können Sie $ nCk $ in der Größenordnung von $ O (1) $ berechnen.
Das Folgende ist ein Beispiel für die Antwort auf diese Frage.
def cmb(n, k, mod, fac, ifac):
"""
Berechne nCk
"""
k = min(k, n-k)
return fac[n] * ifac[k] * ifac[n-k] % mod
def make_tables(mod, n):
"""
Erstellen Sie einen Bodentisch und einen umgekehrten Bodentisch
"""
fac = [1, 1] #Bodentisch ...(1)
ifac = [1, 1] #Reverse-Bodentisch ...(2)
inverse = [0, 1] #Reverse Source Tabelle ...(3)
for i in range(2, n+1):
fac.append((fac[-1] * i) % mod)
inverse.append((-inverse[mod % i] * (mod//i)) % mod)
ifac.append((ifac[-1] * inverse[-1]) % mod)
return fac, ifac
X, Y = map(int, input().split())
#Später, n,Um die Größe von m konstant zu halten
if X > Y:
X, Y = Y, X
dist = X + Y
if dist % 3 != 0:
print(0)
else:
# (+1,+2)Die Anzahl der Bewegungen von n,(+2,+1)Sei m die Anzahl der Bewegungen von)
# total = n + m
#Die folgende Formel lautet 2n+ m = X, n + 2m =Das Ergebnis der Lösung der simultanen Gleichungen von Y.
total = int((X+Y) / 3)
n = X - total
# n <0 oder m<Wenn es 0 ist, kann es nicht erreicht werden
# Y >Weil es X ist, m> n
# n < 0 → 2X - Y < 0
if Y > 2*X:
print(0)
else:
MOD = 10**9 + 7
fac, ifac = make_tables(MOD, total)
ans = cmb(total, n, MOD, fac, ifac)
print(ans)
Dieses Mal ist die zu teilende Zahl $ 10 ^ 9 + 7 $, also könnte ich sie ohne Probleme berechnen, aber es scheint, dass keine Zahl in Ordnung ist. Die Beziehung zwischen der Anzahl der Divisionen $ p $ und $ nCr $ ist
Wird benötigt.
Recommended Posts