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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include "message.h"
#include "futbol.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <numeric>

const int PARAMETER = 5;

inline std::tuple<int, int, int> egcd(int a, int b)
{
    if (a == 0)
        return std::tuple<int, int, int>{b, 0, 1};

    int g, y, x;
    std::tie(g, y, x) = egcd(b % a, a);

    return std::tuple<int, int, int>{g, x - (b / a) * y, y};
}

inline int modinv(int a, int m)
{
    int g, x, y;
    std::tie(g, x, y) = egcd(a, m);

    return (x+m) % m;
}

const int MAX_N = 1000000000;

void run()
{
    using namespace std;

    const int nodes = NumberOfNodes();
    const int id = MyNodeId();

    vector<int> work_offset(nodes+1, 0);

    for (int i = 0; i < nodes; ++i)
    {
        work_offset[i+1] = work_offset[i] + PARAMETER + i;
    }

    const int work_total = work_offset.back();

    const int input_k = GetK();
    const int MAX_K = std::min(input_k, MAX_N - input_k);
    const int p = GetP();

    
    const int work_begin = work_offset[id];
    const int work_end = work_offset[id+1];

    //cerr << ":: Work [" << work_begin << ", " << work_end << ") size = " << work_end-work_begin << endl;

    const int begin_k = 1LL * MAX_K * work_begin / work_total + 1;
    const int end_k = 1LL * MAX_K * work_end / work_total + 1;
    const int k_count = end_k - begin_k;

    //cerr << ":: Computing [" << begin_k << ", " << end_k << ")" << endl;

    std::vector<int> computed(k_count);

    for (int k = begin_k; k < end_k; ++k)
    {
        computed[k-begin_k] = modinv(k, p);
    }


    int answer = 1;
    int state = 1;

    int n;

    if (id == 0)
    {
        n = GetN();
    }
    else
    {
        Receive(id-1);
        n = GetInt(id-1);
        answer = GetInt(id-1);
        state = GetInt(id-1);
    }

    if (n == -1)
    {
        if (id != nodes-1)
        {
            PutInt(id+1, -1);
            PutInt(id+1, -1);
            PutInt(id+1, -1);
            Send(id+1);
        }
        return;
    }

    int actual_k = std::min(input_k, n - input_k);

    const int end2_k = std::min(end_k, actual_k+1);

    //cerr << ":: Joining [" << begin_k << ", " << end2_k << ")" << endl;

    long long sum = 0;

    for (int k = begin_k; k < end2_k; ++k)
    {
        const int inv = computed[k-begin_k];
        
        state = 1LL * state * (n-k+1) % p * inv % p;
        sum += state;
    }
    answer = (answer + sum) % p;

    if (end2_k == actual_k+1)
    {
        cout << answer << endl;

        if (id != nodes-1)
        {
            PutInt(id+1, -1);
            PutInt(id+1, -1);
            PutInt(id+1, -1);
            Send(id+1);
        }
    }
    else
    {
        if (id != nodes-1)
        {
            PutInt(id+1, n);
            PutInt(id+1, answer);
            PutInt(id+1, state);
            Send(id+1);
        }
    }
}

int main()
{
    run();
    return 0;
}