Potrzebujesz pomocy w modach 1000000007 pytania

Question

Jestem słaby w matematyce i zawsze utknąłem z problemami, które wymagają modulo odpowiedź kilka pierwszych nie.

np: (! 500/20) mod 1000000007

znam BigIntegers ale obliczenia modulo po obliczania silni 500 (nawet po użyciu DP) zdaje się ładunek czasu.

Chciałbym wiedzieć, czy istnieje szczególny sposób podejścia/radzenia sobie z takimi problemami.

Oto jeden taki problem, który próbuję rozwiązać w tej chwili: http://www.codechef.com/FEB12/problems/WCOUNT

Byłoby bardzo pomocne, jeśli ktoś może skierować mnie do samouczka lub podejścia do obsługi kodowania tych problemów. Jestem zaznajomiony z Javą i C++.

Answer 1

Kluczem do tych zadań o dużej liczbie modułów nie jest obliczenie pełnego wyniku przed wykonaniem modułu. Należy zmniejszyć moduł w pośrednich kroków, aby utrzymać liczbę mały:

500!/20! = 21 * 22 * 23 * ... * 500 

21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200 

4475671200 mod 1000000007 = 475671172 
475671172 * 28 mod 1000000007 = 318792725 
318792725 * 29 mod 1000000007 = 244988962 
244988962 * 30 mod 1000000007 = 349668811 

... 

31768431 * 500 mod 1000000007 = 884215395 

500!/20! mod 1000000007 = 884215395 

Nie trzeba zmniejszyć moduł na każdym kroku. Po prostu rób to wystarczająco często, aby nie uzyskać zbyt dużej liczby.

---

Należy zauważyć, że maksymalna wartość long wynosi 2^63 - 1. W celu przeprowadzenia 64 bitów mnożenia pomiędzy dwiema wartościami dodatnią liczbą całkowitą (to znaczy jeden z argumentów jest long) nie przepełni long. Możesz bezpiecznie wykonać pozostałą operację % (jeśli jest to również pozytywne) i w razie potrzeby powrócić do liczby całkowitej.

Answer 2

Zacznij od stwierdzenia, że ​​500!/20! jest produktem wszystkich liczb od 21 do 500 włącznie, a następnie sprawdź, czy możesz wykonać mnożenie modulo według pozycji, biorąc pod koniec każdej operacji %1000000007. Powinieneś być teraz w stanie napisać swój program. Uważaj, aby nie przelać liczby: 32 bity mogą nie wystarczyć.

Answer 3

myślę, że to może być w pewnym stopniu użyteczne dla was

for(mod=prime,res=1,i=20;i<501;i++) 
{ 
res*=i; // an obvious step to be done 
if(res>mod) // check if the number exceeds mod 
res%=mod; // so as to avoid the modulo as it is costly operation 
}