Modulo silnia

Odpowiedz Nowy wątek
2013-11-04 20:11
0

Cześć! Moglibyście sprawdzić co jest nie tak z moim kodem? Muszę napisać program, który dla wczytanych liczb "a, b, c" z zakresu 1...1000 ma obliczyć (a+b+c)!/(a!b!c!). Jako, że wynik może być bardzo duży to należy wypisać resztę z dzielenia przez 1 000 000 007.

#include<iostream>
#include<cstdio>
using namespace std;
long long int a, b, c, d = 1000000007, suma, sil_sum = 1, sil_a = 1, sil_b = 1, sil_c = 1;
int main()
{
ios_base::sync_with_stdio(0);
cin >> a >> b >> c;
suma = a+b+c;
for(int i = 1; i <= suma; i++)
{
sil_sum *= i;
sil_sum %= d;
}
for(int i = 1; i <= a; i++)
{
sil_a *= i;
sil_a %= d;
}
for(int i = 1; i <= b; i++)
{
sil_b *= i;
sil_b %= d;
}
for(int i = 1; i <= c; i++)
{
sil_c *= i;
sil_c %= d;
}
cout << (sil_sum/(sil_a*sil_b*sil_c)) % d;
cin.ignore();
getchar();
return 0;
} 

Pozostało 580 znaków

2013-11-04 20:29
1

cout << sil_sum/((sil_a*sil_b*sil_c)%d);

Czy nie można prościej?

#include <iostream>
#include <algorithm>
using namespace std;

int main()
  {
   ios_base::sync_with_stdio(0);
   const unsigned d=1000000007;
   unsigned a,b,c;
   cin>>a>>b>>c;
   if(a<b) swap(a,b);
   if(a<c) swap(a,c);
   unsigned nom=1,den=1;
   for(unsigned i=a+b+c;i>a;--i) nom=(nom*i)%d;
   for(unsigned i=b;i>1;--i) den=(den*i)%d;
   for(unsigned i=c;i>1;--i) den=(den*i)%d;}
   // patrz komentarze oraz post niżej

   cout<<nom/den<<endl;

</del> return 0;
}


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 3x, ostatnio: _13th_Dragon, 2013-11-05 15:37
Dalej nie działa. Dla danych 998, 1, 1 powinno zwrócić 999000 (bo 1000!/998! = 999*1000), a zwraca 28. - Archimondei 2013-11-04 20:32
Więc jeszcze gdzieś się kropnąłeś. - _13th_Dragon 2013-11-04 20:45
No właśnie wiem, ale ani ja ani mój nauczyciel informatyki, nie wiemy gdzie jest błąd. - Archimondei 2013-11-04 20:46
Już wiem co jest nie tak. Zakres long longów był zbyt mały by pomieścić mój program - Archimondei 2013-11-04 21:15
Mój na unsigned się mieści jakby co, więc na pewno nie to. - _13th_Dragon 2013-11-04 21:20
Tak, twój się mieści, bo ty zrobiłeś to sprytniej (skracasz silnię) dlatego twój się mieści. - Archimondei 2013-11-05 17:25

Pozostało 580 znaków

2013-11-05 15:32
2

to dzielenie na końcu jest źle.
Dowód (12/4)%11 = 3 i (12%11)/(4%11) = 0.25.
Tu trzeba wyznaczyć liczbę odwrotną modulo 1000000007, korzystając z rozszerzonego algorytmu Euklidesa.
W podanym przykładzie liczbą odwrotną do 4 modulo 11 jest 3, bo (4*3)%11=1, więc wykonując dzielenie mnożąc liczbą odwrotną dostajemy prawidłowy wynik.

To dzielenie powinno wyglądać tak:

cout<< (nom*libczaOdwrotnaModulo(den, d))%d <<endl;

Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2013-11-06 10:41
Coś tu nadal nie tak: (29680/15265)%30674=1, odwrotność do 15265 to 213 sprawdzamy: (15265*213)%30674=1 mimo to: ((29680%30674)*213)%30674=2996 a nie 1 - _13th_Dragon 2013-11-05 16:24
Wynika to z tego, że 29680%15265!=0. Pamiętaj, że jest to jest arytmetyka modularna, więc to dzielnie tak naprawdę powinno być takie: ((29680+n*30674)/15265)%30674, gdzie n jest takie by wynik z dzielenia przez 15265 był całkowity (stosując arytmetykę modularną zapominamy o tym n i dzięki temu mieścimy się w typach wbudowanych). W tym wypadku będzie to ((29680+1490*30674)/15265)%30674=2996 bo (29680+1490*30674)%15265=0 i wszystko się zgadza. - MarekR22 2013-11-05 16:49
a skąd ci się wzięło to 1490? - _13th_Dragon 2013-11-05 17:35
napisałem przecież że to jest takie n, dla którego da się wykonać to dzielenie całkowite. W arytmetyce modularnej dodawanie wielokrotności cyklu nic nie zmienia. Nie zapominaj, że każda liczba tutaj tak naprawdę jest tu resztą z dzielenia przez 30674. http://www.wolframalpha.com/i[...]9680%2Bn*30674%29%2515265%3D0 - MarekR22 2013-11-05 18:20

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0