#include <bits/stdc++.h> using namespace std; #define PB push_back #define FORE(i, t) for(__typeof(t.begin())i=t.begin();i!=t.end();++i) #define SZ(x) int((x).size()) #define REP(i, n) for(int i=0,_=(n);i<_;++i) #define FOR(i, a, b) for(int i=(a),_=(b);i<=_;++i) #define FORD(i, a, b) for(int i=(a),_=(b);i>=_;--i) typedef long long ll; typedef pair <ll, ll> pll; const int INF = 1e9 + 9; #include "futbol.h" #include "message.h" const ll MAX_NODES = 100; int me; int nodes_count; pll get_range(ll node, ll range_max) { // For range [1..range_max] inclusive. ll a = range_max * node / nodes_count + 1LL; ll b = range_max * (node + 1LL) / nodes_count; return pll(a, b); } ll n, k, p; ll inv(ll base) { ll result = 1; base %= p; ll exp = p - 2; while (exp > 0) { if (exp & 1) { result = (result * base) % p; } base = (base * base) % p; exp /= 2; } return result; } pll compute_mul_and_add(ll a, ll b) { ll mul = 1; ll add = 0; for (ll i = a; i <= b; ++i) { mul = (((mul * (n - i)) % p) * inv(i + 1)) % p; add = (add + mul) % p; } return pll(mul, add); } ll muls[MAX_NODES]; ll adds[MAX_NODES]; int main() { ios::sync_with_stdio(false); me = MyNodeId(); nodes_count = NumberOfNodes(); n = GetN(); k = GetK(); p = GetP(); pll my_range = get_range(me, k); ll my_start = my_range.first - 1; ll my_end = my_range.second - 1; // cout << "me = " << me << " n = " << n << " range=(" << my_start << ", " << my_end << ")" << "\n"; pll mul_add = compute_mul_and_add(my_start, my_end); ll mul = mul_add.first; ll add = mul_add.second; // cout << "node=" << me << " mul=" << mul << " add=" << add << "\n"; if (me > 0) { PutLL(0, mul); PutLL(0, add); Send(0); return 0; } muls[me] = mul; adds[me] = add; FOR (node, 1, nodes_count - 1) { Receive(node); muls[node] = GetLL(node); adds[node] = GetLL(node); } ll result = 1; ll factor = 1; REP(node, nodes_count) { ll add = adds[node]; ll mul = muls[node]; // cout << "i=" << node << " mul=" << mul << " add=" << add << "\n"; result = (result + ((add * factor) % p)) % p; factor = (factor * mul) % p; } cout << result << "\n"; }
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 | #include <bits/stdc++.h> using namespace std; #define PB push_back #define FORE(i, t) for(__typeof(t.begin())i=t.begin();i!=t.end();++i) #define SZ(x) int((x).size()) #define REP(i, n) for(int i=0,_=(n);i<_;++i) #define FOR(i, a, b) for(int i=(a),_=(b);i<=_;++i) #define FORD(i, a, b) for(int i=(a),_=(b);i>=_;--i) typedef long long ll; typedef pair <ll, ll> pll; const int INF = 1e9 + 9; #include "futbol.h" #include "message.h" const ll MAX_NODES = 100; int me; int nodes_count; pll get_range(ll node, ll range_max) { // For range [1..range_max] inclusive. ll a = range_max * node / nodes_count + 1LL; ll b = range_max * (node + 1LL) / nodes_count; return pll(a, b); } ll n, k, p; ll inv(ll base) { ll result = 1; base %= p; ll exp = p - 2; while (exp > 0) { if (exp & 1) { result = (result * base) % p; } base = (base * base) % p; exp /= 2; } return result; } pll compute_mul_and_add(ll a, ll b) { ll mul = 1; ll add = 0; for (ll i = a; i <= b; ++i) { mul = (((mul * (n - i)) % p) * inv(i + 1)) % p; add = (add + mul) % p; } return pll(mul, add); } ll muls[MAX_NODES]; ll adds[MAX_NODES]; int main() { ios::sync_with_stdio(false); me = MyNodeId(); nodes_count = NumberOfNodes(); n = GetN(); k = GetK(); p = GetP(); pll my_range = get_range(me, k); ll my_start = my_range.first - 1; ll my_end = my_range.second - 1; // cout << "me = " << me << " n = " << n << " range=(" << my_start << ", " << my_end << ")" << "\n"; pll mul_add = compute_mul_and_add(my_start, my_end); ll mul = mul_add.first; ll add = mul_add.second; // cout << "node=" << me << " mul=" << mul << " add=" << add << "\n"; if (me > 0) { PutLL(0, mul); PutLL(0, add); Send(0); return 0; } muls[me] = mul; adds[me] = add; FOR (node, 1, nodes_count - 1) { Receive(node); muls[node] = GetLL(node); adds[node] = GetLL(node); } ll result = 1; ll factor = 1; REP(node, nodes_count) { ll add = adds[node]; ll mul = muls[node]; // cout << "i=" << node << " mul=" << mul << " add=" << add << "\n"; result = (result + ((add * factor) % p)) % p; factor = (factor * mul) % p; } cout << result << "\n"; } |