Dans les concours de programmation, lorsque la réponse est très grande, le problème de trouver le reste divisé par un nombre premier se pose souvent. J'ai appris à penser à un tel problème, je vais donc le résumer. L'exemple de code est essentiellement Python 2.7. Référence: TopCoder Trends and Countermeasures 4 (C ++ Edition: Counting)
Vous n'avez qu'à en demander trop à chaque fois que vous faites un calcul.
Après avoir ajouté, demandez trop.
mod = 1000000007
def add(a, b):
return (a + b) % mod
Dans le cas de Python, vous pouvez le tirer sans réfléchir et en demander trop. Si la langue exige trop de valeur négative, il n'y a rien à faire attention.
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
Quand je l'ai essayé avec C, c'est devenu une valeur négative. Dans ce cas, il semble préférable d'ajouter 1000000007 à «a» et de soustraire «b».
#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
}
Le compilateur a utilisé:
$ 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
Multipliez-vous trop et prenez plus.
mod = 1000000007
def mul(a, b):
return ((a % mod) * (b % mod)) % mod
Soudain, le petit théorème de Fermat sort et j'ai peur. D'une certaine manière, cela semble difficile. Je ne suis pas sûr que ce soit une division pour le moment, alors j'aimerais régler la question sur la multiplication.
a \div b = a \times b^{-1}
Voilà ce que c'est. Par conséquent, je veux trop trouver l'inverse de «b» dans le monde. Ensuite, nous utilisons le théorème de Fermat pour trouver l'inverse. En ce qui concerne le processus, si vous regardez la page de référence, le résultat semble être «b» à la puissance 1000000005e. En d'autres termes, en division, le calcul suivant doit être fait.
a \div b = a \times b^{1000000005} (mod 1000000007)
Cette fois, nous devons faire un calcul difficile de «b» à la puissance de 1000000005, mais nous pouvons utiliser la méthode de puissance dichotomique pour cela. Commencez par trouver le carré, utilisez-le pour trouver la 4ème puissance, puis utilisez-le pour trouver la 8ème puissance, et ainsi de suite, c'est beaucoup plus rapide que de multiplier «b» par 1000000005 fois. C'est donc une histoire.
Pour résumer ce qui précède, la division est la suivante.
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
Ça a l'air bien, mais ce n'est pas intuitif ...
Je l'ai essayé. C'est un problème de calculer la combinaison. AtCoder Beginner Contest 042: D --Iroha-chan et carrés
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
Dans le calcul de combinaison, la division est effectuée par la multiplication, donc trouvez l'élément inverse de la multiplication qui semble nécessaire à l'avance. À ce moment-là, si vous calculez en utilisant ce qui suit, cela semble être rapide car vous n'avez pas à calculer plusieurs fois la puissance 1000000005.
n!^{-1} = (n+1)!^{-1} \times (n+1)
Après cela, je pourrais le faire en ajoutant correctement % mod.
Pour être honnête, cela n'a pas l'air correct, mais je pense que c'est probablement fait parce que j'ai AC. Jusqu'à présent, je ne pouvais pas entrer dans le code parce que j'avais peur du théorème de Fermat, donc j'ai l'impression d'avoir fait des progrès.
Recommended Posts