Modulo silnia

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;
}
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
```cpp cout<nom/den<<endl; ``` </del="``` &lt;/del"> return 0; } ```
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;

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