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
#include "message.h"
#include "futbol.h"

#include <cstdio>
#include <vector>

using namespace std;

typedef long long LL;

int n, k, p;

LL psum(LL a, LL b) {
  return (a+b) % p;
}
LL pmul(LL a, LL b) {
  return (a*b) % p;
}

LL ppow(LL a, LL b) {
  if (b == 0) return 1;
  LL r = ppow(pmul(a, a), b/2);
  if (b&1) return pmul(r, a);
  return r;
}

LL pinv(LL a) {
  return ppow(a, p-2);
}

void FillBottom(vector<LL>& e, int a, int b) {
  LL f = 1;
  for (int i=a; i<b; ++i) {
    if (i == 0) continue;
    f = pmul(f, pinv(i));
    e[i-a] = f;
  }
}

void FillTop(vector<LL>& e, int a, int b) {
  LL f = 1;
  for (int i=a; i<b; ++i) {
    if (i == 0) continue;
    f = pmul(f, n-i+1);
    e[i-a] = pmul(e[i-a], f);
  }
}

LL Sum(const vector<LL>& e, int a, int b, LL f) {
  LL sum = 0;
  for (LL x : e) {
    sum += pmul(x, f);
  }
  return sum % p;
}

int main() {
  n = GetN();
  k = GetK(); ++k;
  p = GetP();

  int nodes = NumberOfNodes();
  int node_id = MyNodeId();
  int next_node_id = (node_id + 1) % nodes;
  int prev_node_id = (node_id + nodes - 1) % nodes;

  int a = k * node_id / nodes;
  int b = k * (node_id + 1) / nodes;

  vector<LL> e(b-a, 1);
  FillBottom(e, a, b);

  if (n != 0) {
    FillTop(e, a, b);
  }

  LL f = 1;
  LL sum = 0;
  if (node_id == 0) {
    sum = Sum(e, a, b, f);
    if (!e.empty()) {
      f = pmul(f, e.back());      
    }
    PutLL(next_node_id, n);
    PutLL(next_node_id, f);
    PutLL(next_node_id, sum);
    Send(next_node_id);
    Receive(prev_node_id);
    GetLL(prev_node_id); // n
    GetLL(prev_node_id); // f
    printf("%lld\n", GetLL(prev_node_id)); // sum
  } else {
    Receive(prev_node_id);
    if (n != 0) {
      GetLL(prev_node_id); // n
    } else {
      n = GetLL(prev_node_id);
      FillTop(e, a, b);
    }
    f = GetLL(prev_node_id);
    sum = GetLL(prev_node_id);
    sum = (sum + Sum(e, a, b, f)) % p;
    if (!e.empty()) {
      f = pmul(f, e.back());
    }
    PutLL(next_node_id, n);
    PutLL(next_node_id, f);
    PutLL(next_node_id, sum);
    Send(next_node_id);
  }
  return 0;
}