#include "message.h" #include "futbol.h" #include <iostream> using namespace std; long long n, k, p; long long wynik; long long silnie[101]; long long potModulo(long long x, long long c, long long mod) { if(c == 0) return 1; if(c % 2 == 1) return (x * potModulo(x, c - 1, mod)) % mod; long long t = potModulo(x, c / 2, mod); return (t * t) % mod; } long long obliczSilnie(long long x) { long long wynik = silnie[x / (10 * 1000 * 1000)]; for(int i = x / (10 * 1000 * 1000) + 1; i <= x; i++) { wynik = (wynik * i) % p; } return wynik; } int main() { n = GetN(); k = GetK(); p = GetP(); long long silnia = 1; for(int i = 10 * 1000 * 1000 * MyNodeId() + 1; i <= 10 * 1000 * 1000 * (MyNodeId() + 1); i++) { silnia = (silnia * i) % p; } silnie[0] = 1; silnie[1] = silnia; if(MyNodeId() != 0) { PutLL(0, silnia); Send(0); } else { for(int i = 1; i < NumberOfNodes(); i++) { Receive(i); silnie[i + 1] = (silnie[i] * GetLL(i)) % p; } long long silniaN = obliczSilnie(n); long long silniaK = obliczSilnie(k); long long silniaNMK = obliczSilnie(n - k); long long silniaKOdwrotnosc = potModulo(silniaK, p - 2, p); long long silniaNMKOdwrotnosc = potModulo(silniaNMK, p - 2, p); for(int i = k; i >= 0; i--) { wynik = (wynik + (((silniaN * silniaKOdwrotnosc) % p) * silniaNMKOdwrotnosc) % p) % p; silniaKOdwrotnosc = (silniaKOdwrotnosc * i) % p; silniaNMKOdwrotnosc = (silniaNMKOdwrotnosc * potModulo(n - i + 1, p - 2, p)) % p; } cout << wynik; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include "message.h" #include "futbol.h" #include <iostream> using namespace std; long long n, k, p; long long wynik; long long silnie[101]; long long potModulo(long long x, long long c, long long mod) { if(c == 0) return 1; if(c % 2 == 1) return (x * potModulo(x, c - 1, mod)) % mod; long long t = potModulo(x, c / 2, mod); return (t * t) % mod; } long long obliczSilnie(long long x) { long long wynik = silnie[x / (10 * 1000 * 1000)]; for(int i = x / (10 * 1000 * 1000) + 1; i <= x; i++) { wynik = (wynik * i) % p; } return wynik; } int main() { n = GetN(); k = GetK(); p = GetP(); long long silnia = 1; for(int i = 10 * 1000 * 1000 * MyNodeId() + 1; i <= 10 * 1000 * 1000 * (MyNodeId() + 1); i++) { silnia = (silnia * i) % p; } silnie[0] = 1; silnie[1] = silnia; if(MyNodeId() != 0) { PutLL(0, silnia); Send(0); } else { for(int i = 1; i < NumberOfNodes(); i++) { Receive(i); silnie[i + 1] = (silnie[i] * GetLL(i)) % p; } long long silniaN = obliczSilnie(n); long long silniaK = obliczSilnie(k); long long silniaNMK = obliczSilnie(n - k); long long silniaKOdwrotnosc = potModulo(silniaK, p - 2, p); long long silniaNMKOdwrotnosc = potModulo(silniaNMK, p - 2, p); for(int i = k; i >= 0; i--) { wynik = (wynik + (((silniaN * silniaKOdwrotnosc) % p) * silniaNMKOdwrotnosc) % p) % p; silniaKOdwrotnosc = (silniaKOdwrotnosc * i) % p; silniaNMKOdwrotnosc = (silniaNMKOdwrotnosc * potModulo(n - i + 1, p - 2, p)) % p; } cout << wynik; } return 0; } |