// Karol Kosinski 2018 #include "message.h" #include "futbol.h" #include <cstdio> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FOD(i,b,a) for(int i=(b)-1;i>=(a);--i) //#define DEBUG(x...) printf(x); #define DEBUG(x...) using namespace std; typedef long long LL; struct gcd { LL x, y; }; gcd gcd_fun(LL a, LL b) { if(b == 0) return (gcd){1, 0}; gcd t = gcd_fun(b, a % b); return (gcd){t.y, t.x - (a / b) * t.y}; } LL pow2(int a, int p) { LL res = 1, y = 2; while(a > 0) { if((a & 1) == 1) res = (res * y) % p; y = (y * y) % p; a >>= 1; } return res; } int main() { int id = MyNodeId(), nodes = NumberOfNodes(); int n = GetN(), kk = GetK(), p = GetP(); if(n == kk) { if(id == 0) { printf("%lld\n", pow2(n, p)); } return 0; } int k = (2 * kk <= n) ? kk : (n - kk - 1); int start = LL(id) * k / nodes; int finish = LL(id + 1) * k / nodes; LL sum = 1, fac = 1; FOD(i,finish,start) { LL aux = (gcd_fun(p, i + 1).y + p) % p; LL x = ((n - i) * aux) % p; sum = (1 + x * sum) % p; fac = (fac * x) % p; } if(id != 0) { PutLL(0, (sum + p - 1) % p); PutLL(0, fac); Send(0); } else { FOR(i,1,nodes) { Receive(i); LL s = GetLL(i); LL f = GetLL(i); sum = (sum + fac * s) % p; fac = (fac * f) % p; } if(k == kk) printf("%lld\n", sum); else printf("%lld\n", (pow2(n, p) - sum + p) % p); } 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 75 76 77 78 79 | // Karol Kosinski 2018 #include "message.h" #include "futbol.h" #include <cstdio> #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FOD(i,b,a) for(int i=(b)-1;i>=(a);--i) //#define DEBUG(x...) printf(x); #define DEBUG(x...) using namespace std; typedef long long LL; struct gcd { LL x, y; }; gcd gcd_fun(LL a, LL b) { if(b == 0) return (gcd){1, 0}; gcd t = gcd_fun(b, a % b); return (gcd){t.y, t.x - (a / b) * t.y}; } LL pow2(int a, int p) { LL res = 1, y = 2; while(a > 0) { if((a & 1) == 1) res = (res * y) % p; y = (y * y) % p; a >>= 1; } return res; } int main() { int id = MyNodeId(), nodes = NumberOfNodes(); int n = GetN(), kk = GetK(), p = GetP(); if(n == kk) { if(id == 0) { printf("%lld\n", pow2(n, p)); } return 0; } int k = (2 * kk <= n) ? kk : (n - kk - 1); int start = LL(id) * k / nodes; int finish = LL(id + 1) * k / nodes; LL sum = 1, fac = 1; FOD(i,finish,start) { LL aux = (gcd_fun(p, i + 1).y + p) % p; LL x = ((n - i) * aux) % p; sum = (1 + x * sum) % p; fac = (fac * x) % p; } if(id != 0) { PutLL(0, (sum + p - 1) % p); PutLL(0, fac); Send(0); } else { FOR(i,1,nodes) { Receive(i); LL s = GetLL(i); LL f = GetLL(i); sum = (sum + fac * s) % p; fac = (fac * f) % p; } if(k == kk) printf("%lld\n", sum); else printf("%lld\n", (pow2(n, p) - sum + p) % p); } return 0; } |