Bei Programmierwettbewerben tritt häufig das Problem auf, den Rest geteilt durch eine Primzahl zu finden, wenn die Antwort sehr groß ist. Ich habe gelernt, über ein solches Problem nachzudenken, deshalb werde ich es zusammenfassen. Der Beispielcode ist im Grunde Python 2.7. Referenz: TopCoder Trends und Gegenmaßnahmen 4 (C ++ Edition: Counting)
Sie müssen jedes Mal, wenn Sie eine Berechnung durchführen, zu viel verlangen.
Fragen Sie nach dem Hinzufügen einfach zu viel.
mod = 1000000007
def add(a, b):
return (a + b) % mod
Im Fall von Python können Sie es ohne nachzudenken ziehen und dann zu viel verlangen. Wenn die Sprache zu viel negativen Wert erfordert, gibt es nichts, worüber man vorsichtig sein muss.
mod = 1000000007
def sub(a, b):
return (a + mod - b) % mod
def sub_(a, b):
return (a - b) % mod
print sub(1, 2) # => 1000000006
print sub_(1, 2) # => 1000000006
Als ich es mit C versuchte, wurde es ein negativer Wert. In diesem Fall scheint es besser, 1000000007 zu "a" zu addieren und dann "b" zu subtrahieren.
#include <stdio.h>
int mod = 1000000007;
int sub(a, b) {
return (a + mod - b) % mod;
}
int sub_(a, b) {
return (a - b) % mod;
}
int main(void){
printf("%d\n", sub(1, 2)); // => 1000000006
printf("%d\n", sub_(1, 2)); // => -1
}
Der verwendete Compiler:
$ gcc -v
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin16.0.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
Multiplizieren Sie sich zu viel und nehmen Sie mehr.
mod = 1000000007
def mul(a, b):
return ((a % mod) * (b % mod)) % mod
Plötzlich kommt Fermats kleiner Satz heraus und ich habe Angst. Irgendwie scheint es schwierig. Ich bin mir nicht sicher, ob es sich vorerst um eine Division handelt, daher möchte ich sie auf Multiplikation beschränken.
a \div b = a \times b^{-1}
Das ist es. Deshalb möchte ich die Umkehrung von "b" in der Welt zu sehr finden. Dann verwenden wir den Satz von Fermat, um die Umkehrung zu finden. Wenn Sie sich die Referenzseite ansehen, scheint das Ergebnis "b" für die 1000000005. Potenz zu sein. Mit anderen Worten, in Division sollte die folgende Berechnung durchgeführt werden.
a \div b = a \times b^{1000000005} (mod 1000000007)
Dieses Mal müssen wir eine schwierige Berechnung von "b" mit der Potenz von 1000000005 durchführen, aber wir können hierfür die dichotome Potenzmethode verwenden.
Wenn Sie das Quadrat zuerst finden, verwenden Sie es, um die 4. Potenz zu finden, und verwenden Sie es dann, um die 8. Potenz zu finden, und so weiter. Sie können es viel schneller finden, als b mit 1000000005 mal zu multiplizieren. Daher ist es eine Geschichte.
Um das Obige zusammenzufassen, ist die Unterteilung wie folgt.
mod = 1000000007
def mul(a, b):
return ((a % mod) * (b % mod)) % mod
def power(x, y):
if y == 0 : return 1
elif y == 1 : return x % mod
elif y % 2 == 0 : return power(x, y/2)**2 % mod
else : return power(x, y/2)**2 * x % mod
def div(a, b):
return mul(a, power(b, mod-2))
print div(6, 3) # => 2
print div(10, 2) # => 5
print div(3000000000, 2) # => 499999993
print div(45000000000, 5) # => 999999944
print div(4000000000, 2000000000) # => 2
print div(45000000000, 5000000000) # => 9
Es sieht gut aus, ist aber nicht intuitiv ...
Ich versuchte es. Es ist ein Problem, die Kombination zu berechnen. AtCoder-Anfängerwettbewerb 042: D - Iroha richtig quadratisch
mod = 1000000007
H, W, A, B = map(int, raw_input().split())
factorial = [1]
for n in xrange(1, H+W):
factorial.append(factorial[n-1]*n%mod)
def power(x, y):
if y == 0 : return 1
elif y == 1 : return x % mod
elif y % 2 == 0 : return power(x, y/2)**2 % mod
else : return power(x, y/2)**2 * x % mod
inverseFactorial = [0] * (H+W)
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in xrange(H+W-2, -1, -1):
inverseFactorial[n] = inverseFactorial[n+1] * (n+1) % mod
def combi(n, m):
return factorial[n] * inverseFactorial[m] * inverseFactorial[n-m] % mod
sum = 0
for i in xrange(B+1, W+1):
sum = (sum + combi(H-A-1+i-1, i-1) * combi(A-1+W-i, W-i)) % mod
print sum
Bei der Kombinationsberechnung wird die Division durch die Multiplikation durchgeführt. Suchen Sie daher das inverse Element der Multiplikation, das im Voraus als notwendig erscheint. Wenn Sie zu diesem Zeitpunkt Folgendes berechnen, scheint dies schnell zu sein, da Sie die Leistung von 1000000005 nicht viele Male berechnen müssen.
n!^{-1} = (n+1)!^{-1} \times (n+1)
Um ehrlich zu sein, sieht es nicht richtig aus, aber ich denke, es ist wahrscheinlich gemacht, weil ich AC habe. Bis jetzt konnte ich nicht in den Code einsteigen, weil ich Angst vor dem Satz von Fermat hatte, also habe ich das Gefühl, dass ich mich ein wenig vorwärts bewegen konnte.
Recommended Posts