Note d'étude de problème à demander trop divisé par 1000000007

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)

Que devrais-je faire?

Vous n'avez qu'à en demander trop à chaque fois que vous faites un calcul.

En cas d'ajout

Après avoir ajouté, demandez trop.

mod = 1000000007

def add(a, b):
    return (a + b) % mod

Dans le cas de la soustraction

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

En cas de multiplication

Multipliez-vous trop et prenez plus.

mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

En cas de division

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 vais essayer de résoudre un problème

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.

en conclusion

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

Note d'étude de problème à demander trop divisé par 1000000007
Mémo pour demander des KPI avec python
[Pour les débutants] Comment étudier la programmation Mémo privé
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer Chapitre 10 Introduction à Cupy
Mémo d'apprentissage Python pour l'apprentissage automatique par Chainer Chapitre 9 Introduction à scikit-learn
Décidez pour qui voter par loterie
Mémo d'étude Python & Machine Learning ④: Machine Learning par rétro-propagation