#include "message.h" #include "futbol.h" #include <cstdio> using LL = long long; const int MAX = 2 * 100 * 1000 * 1000, NODES = 100; const int BLOCK_SIZE = MAX / NODES; int P, K, N, res; int fac_high[BLOCK_SIZE + 1], fac_low[BLOCK_SIZE + 1], prefsum[BLOCK_SIZE + 1]; int max(int a, int b) { return (a > b ? a : b); } LL pow(int a, int n, int mod) { if (n == 0) return 1; int tmp = pow((a*(LL)a)%mod, n/2, mod); return (n%2 ? (tmp * (LL)a)%mod : tmp); } int main() { int node = MyNodeId(); int beg_high = BLOCK_SIZE * node; int end_high = BLOCK_SIZE * (node + 1); P = GetP(); K = GetK(); if (node == 0) N = GetN(); int inv_2 = pow(2, P-2, P); fac_high[0] = 1; for (int i=beg_high+1; i<=end_high; i++) fac_high[i-beg_high] = (fac_high[i-beg_high-1] * (LL)i) % P; int beg_low = beg_high - K; int end_low = end_high - K; bool special = (beg_low < 0 && end_low >= 0); for (int i=0; i<=BLOCK_SIZE; i++) fac_low[i] = 1; for (int i=max(1, beg_low+1); i<=end_low; i++) fac_low[i-beg_low] = (fac_low[i-beg_low-1] * (LL)i) % P; prefsum[0] = 0; int start = max(1, beg_low+1); if (special) start--; for (int i=start; i<=end_low; i++) { int x = (fac_high[i-beg_low] * pow(fac_low[i-beg_low], P-2, P)) % P; x = (x * pow(inv_2, K+i+1, P)) % P; prefsum[i-beg_low] = ((i == 0 ? 0 : prefsum[i-beg_low-1]) + x) % P; } int k_fac = 0; if (node > 0) { Receive(node-1); N = GetInt(node-1); fac_low[0] = GetInt(node-1); fac_high[0] = GetInt(node-1); res = GetInt(node-1); k_fac = GetInt(node-1); } if (beg_high < K && K <= end_high) k_fac = (fac_high[0] * (LL)fac_high[K-beg_high]) % P; int max = N - K - 1; if ((max > beg_low || (special && max >= beg_low)) && end_low >= 0) { if (max > end_low) max = end_low; int x = prefsum[max-beg_low]; x = (x * (LL)fac_high[0]) % P; x = (x * pow(fac_low[0], P-2, P)) % P; res = (res + x) % P; } if (node == NODES - 1) { res = (res * pow(k_fac, P-2, P)) % P; res = (1 - res + P) % P; res = (res * pow(2, N, P)) % P; if (res < 0) res += P; printf("%d\n", res); } else { PutInt(node+1, N); PutInt(node+1, (fac_low[0] * (LL)fac_low[end_low-beg_low]) % P); PutInt(node+1, (fac_high[0] * (LL)fac_high[end_high-beg_high]) % P); PutInt(node+1, res); PutInt(node+1, k_fac); Send(node+1); } 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 80 81 82 83 84 85 86 | #include "message.h" #include "futbol.h" #include <cstdio> using LL = long long; const int MAX = 2 * 100 * 1000 * 1000, NODES = 100; const int BLOCK_SIZE = MAX / NODES; int P, K, N, res; int fac_high[BLOCK_SIZE + 1], fac_low[BLOCK_SIZE + 1], prefsum[BLOCK_SIZE + 1]; int max(int a, int b) { return (a > b ? a : b); } LL pow(int a, int n, int mod) { if (n == 0) return 1; int tmp = pow((a*(LL)a)%mod, n/2, mod); return (n%2 ? (tmp * (LL)a)%mod : tmp); } int main() { int node = MyNodeId(); int beg_high = BLOCK_SIZE * node; int end_high = BLOCK_SIZE * (node + 1); P = GetP(); K = GetK(); if (node == 0) N = GetN(); int inv_2 = pow(2, P-2, P); fac_high[0] = 1; for (int i=beg_high+1; i<=end_high; i++) fac_high[i-beg_high] = (fac_high[i-beg_high-1] * (LL)i) % P; int beg_low = beg_high - K; int end_low = end_high - K; bool special = (beg_low < 0 && end_low >= 0); for (int i=0; i<=BLOCK_SIZE; i++) fac_low[i] = 1; for (int i=max(1, beg_low+1); i<=end_low; i++) fac_low[i-beg_low] = (fac_low[i-beg_low-1] * (LL)i) % P; prefsum[0] = 0; int start = max(1, beg_low+1); if (special) start--; for (int i=start; i<=end_low; i++) { int x = (fac_high[i-beg_low] * pow(fac_low[i-beg_low], P-2, P)) % P; x = (x * pow(inv_2, K+i+1, P)) % P; prefsum[i-beg_low] = ((i == 0 ? 0 : prefsum[i-beg_low-1]) + x) % P; } int k_fac = 0; if (node > 0) { Receive(node-1); N = GetInt(node-1); fac_low[0] = GetInt(node-1); fac_high[0] = GetInt(node-1); res = GetInt(node-1); k_fac = GetInt(node-1); } if (beg_high < K && K <= end_high) k_fac = (fac_high[0] * (LL)fac_high[K-beg_high]) % P; int max = N - K - 1; if ((max > beg_low || (special && max >= beg_low)) && end_low >= 0) { if (max > end_low) max = end_low; int x = prefsum[max-beg_low]; x = (x * (LL)fac_high[0]) % P; x = (x * pow(fac_low[0], P-2, P)) % P; res = (res + x) % P; } if (node == NODES - 1) { res = (res * pow(k_fac, P-2, P)) % P; res = (1 - res + P) % P; res = (res * pow(2, N, P)) % P; if (res < 0) res += P; printf("%d\n", res); } else { PutInt(node+1, N); PutInt(node+1, (fac_low[0] * (LL)fac_low[end_low-beg_low]) % P); PutInt(node+1, (fac_high[0] * (LL)fac_high[end_high-beg_high]) % P); PutInt(node+1, res); PutInt(node+1, k_fac); Send(node+1); } return 0; } |