#include "message.h" #include "futbol.h" #include "bits/stdc++.h" //int GetN() {return 1e9;} //int GetK() {return 1e9-1;} //int GetP() {return 1e9 + 7;} using namespace std; const int N = 10 * 1000 * 1000 + 7; int id, nodes, n, k, p; int rev = 0; int power(int a, int n, int p) { int r = 1; while (n > 0) { if (n % 2) { r = (1LL * r * a) % p; } a = (1LL * a * a) % p; n /= 2; } return r; } int inv(int a, int p){ return a > 1 ? p - 1LL * inv(p % a, a) * p / a : 1; } void solveMultipleInstances() { if (n == 0) { PutInt(0, 0); Send(0); return; } int block_len = (k + nodes) / nodes; int l = id * block_len, r = min(k + 1, (id + 1) * block_len); int rs = 0; int cur = 1; for (int i = l; i < r; ++i) { rs += cur; if (rs >= p) rs -= p; cur = (1LL * cur * (n - i)) % p; cur = (1LL * cur * inv(i + 1, p)) % p; } if (id != 0) { PutInt(0, rs); PutInt(0, cur); Send(0); return; } for (int i = 1; i < nodes; ++i) { Receive(i); int r = GetInt(i); int last = GetInt(i); rs = (rs + 1LL * r * cur) % p; cur = (1LL * cur * last) % p; } if (rev) rs = (power(2, n, p) + p - rs) % p; cout << rs << '\n'; } void solveOneInstance() { if (id != 0) { return; } int rs = 0; int cur = 1; for (int i = 0; i <= k; ++i) { rs += cur; if (rs >= p) rs -= p; cur = (1LL * cur * (n - i)) % p; cur = (1LL * cur * inv(i + 1, p)) % p; } if (rev) rs = (power(2, n, p) + p - rs) % p; cout << rs << '\n'; } int main() { id = MyNodeId(); nodes = NumberOfNodes(); n = GetN(); k = GetK(); p = GetP(); if (n > 0 && k > n - k - 1) { k = n - k - 1; rev = 1; } if (k < 1e6) { solveOneInstance(); } else { solveMultipleInstances(); } }
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 "message.h" #include "futbol.h" #include "bits/stdc++.h" //int GetN() {return 1e9;} //int GetK() {return 1e9-1;} //int GetP() {return 1e9 + 7;} using namespace std; const int N = 10 * 1000 * 1000 + 7; int id, nodes, n, k, p; int rev = 0; int power(int a, int n, int p) { int r = 1; while (n > 0) { if (n % 2) { r = (1LL * r * a) % p; } a = (1LL * a * a) % p; n /= 2; } return r; } int inv(int a, int p){ return a > 1 ? p - 1LL * inv(p % a, a) * p / a : 1; } void solveMultipleInstances() { if (n == 0) { PutInt(0, 0); Send(0); return; } int block_len = (k + nodes) / nodes; int l = id * block_len, r = min(k + 1, (id + 1) * block_len); int rs = 0; int cur = 1; for (int i = l; i < r; ++i) { rs += cur; if (rs >= p) rs -= p; cur = (1LL * cur * (n - i)) % p; cur = (1LL * cur * inv(i + 1, p)) % p; } if (id != 0) { PutInt(0, rs); PutInt(0, cur); Send(0); return; } for (int i = 1; i < nodes; ++i) { Receive(i); int r = GetInt(i); int last = GetInt(i); rs = (rs + 1LL * r * cur) % p; cur = (1LL * cur * last) % p; } if (rev) rs = (power(2, n, p) + p - rs) % p; cout << rs << '\n'; } void solveOneInstance() { if (id != 0) { return; } int rs = 0; int cur = 1; for (int i = 0; i <= k; ++i) { rs += cur; if (rs >= p) rs -= p; cur = (1LL * cur * (n - i)) % p; cur = (1LL * cur * inv(i + 1, p)) % p; } if (rev) rs = (power(2, n, p) + p - rs) % p; cout << rs << '\n'; } int main() { id = MyNodeId(); nodes = NumberOfNodes(); n = GetN(); k = GetK(); p = GetP(); if (n > 0 && k > n - k - 1) { k = n - k - 1; rev = 1; } if (k < 1e6) { solveOneInstance(); } else { solveMultipleInstances(); } } |