#include <bits/stdc++.h> #include "futbol.h" #include "message.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> Pii; typedef vector<Pii> vpii; typedef vector<int> vi; typedef vector<ll> vll; #define pb push_back #define fst first #define snd second //int GetN() { return 1e9; } //int GetK() { return 500000000; } //int GetP() { return 1000000000 + 7;} //int GetElement(int i) { return 1e6; } int nodes; int ja; ll n; ll k; ll p; bool fliped; void init() { nodes = NumberOfNodes(); ja = MyNodeId(); n = GetN(); k = GetK(); p = GetP(); if(n - k - 1 < k) { k = n - k - 1; fliped = true; } } void wyslij(int x, vll V) { for(ll y : V) { PutLL(x, y); //printf("Wysylam %lld\n", y); } Send(x); } vll odbierz(int x, int ile) { vll res; Receive(x); for(int i = 0; i < ile; ++i) { res.pb(GetLL(x)); //printf("Odbieram %lld\n", res.back()); } return res; } ll pot(ll x, ll exp) { ll res = 1; while(exp) { if(exp & 1) res = res * x % p; x = x * x % p; exp >>= 1; } return res; } ll rev(ll x) { return pot(x, p-2); } int main() { init(); ll res = 0; ll b = 1ll * ja * (k+1) / nodes; ll e = 1ll * (ja + 1) * (k+1) / nodes; //printf("b = %lld e = %lld\n", b, e); ll suma = 0; ll cur = 1; vll chuj; ll sil = 1; for(ll i = b; i < e; ++i) { // rano przerobić, żeby zapierdalało chuj.pb(cur); sil = sil * (i + 1) % p; ///cur = cur * (n - i) % p * rev(i + 1) % p; cur = cur * (n - i) % p; } sil = rev(sil); cur = cur * sil % p; for(int i = e - 1; i >= b; --i) { sil = sil * (i + 1) % p; suma += chuj.back() * sil % p; chuj.pop_back(); } //printf("cur = %lld\n", cur); if(ja == 0) { for(int i = 1; i < nodes; ++i) { vll v = odbierz(i, 2); suma += cur * v[0] % p; cur = cur * v[1] % p; } if(fliped) { suma = (pot(2, n) - suma % p + p) % p; } printf("%lld\n", suma % p); } else { wyslij(0, {suma % p, cur}); } }
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #include <bits/stdc++.h> #include "futbol.h" #include "message.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> Pii; typedef vector<Pii> vpii; typedef vector<int> vi; typedef vector<ll> vll; #define pb push_back #define fst first #define snd second //int GetN() { return 1e9; } //int GetK() { return 500000000; } //int GetP() { return 1000000000 + 7;} //int GetElement(int i) { return 1e6; } int nodes; int ja; ll n; ll k; ll p; bool fliped; void init() { nodes = NumberOfNodes(); ja = MyNodeId(); n = GetN(); k = GetK(); p = GetP(); if(n - k - 1 < k) { k = n - k - 1; fliped = true; } } void wyslij(int x, vll V) { for(ll y : V) { PutLL(x, y); //printf("Wysylam %lld\n", y); } Send(x); } vll odbierz(int x, int ile) { vll res; Receive(x); for(int i = 0; i < ile; ++i) { res.pb(GetLL(x)); //printf("Odbieram %lld\n", res.back()); } return res; } ll pot(ll x, ll exp) { ll res = 1; while(exp) { if(exp & 1) res = res * x % p; x = x * x % p; exp >>= 1; } return res; } ll rev(ll x) { return pot(x, p-2); } int main() { init(); ll res = 0; ll b = 1ll * ja * (k+1) / nodes; ll e = 1ll * (ja + 1) * (k+1) / nodes; //printf("b = %lld e = %lld\n", b, e); ll suma = 0; ll cur = 1; vll chuj; ll sil = 1; for(ll i = b; i < e; ++i) { // rano przerobić, żeby zapierdalało chuj.pb(cur); sil = sil * (i + 1) % p; ///cur = cur * (n - i) % p * rev(i + 1) % p; cur = cur * (n - i) % p; } sil = rev(sil); cur = cur * sil % p; for(int i = e - 1; i >= b; --i) { sil = sil * (i + 1) % p; suma += chuj.back() * sil % p; chuj.pop_back(); } //printf("cur = %lld\n", cur); if(ja == 0) { for(int i = 1; i < nodes; ++i) { vll v = odbierz(i, 2); suma += cur * v[0] % p; cur = cur * v[1] % p; } if(fliped) { suma = (pot(2, n) - suma % p + p) % p; } printf("%lld\n", suma % p); } else { wyslij(0, {suma % p, cur}); } } |