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
147
148
#include "message.h"
#include "futbol.h"
#include <iostream>
#include <vector>



using namespace std;

template <class T>
inline T sqr(const T x ){
    return x*x;
}
template <class T>
T modpower(T const a, const int ex,T const m){
    if (ex==0) return T(1);
    else {
        if (ex%2==1)    {
            return (a*modpower(a,ex-1,m))%m;
        } else {
            return sqr(modpower(a,ex/2,m))%m;
        }
    }
}


int64_t mul_inv(int64_t a, int64_t m)
{
    int64_t m0 = m, t, q;
    int64_t x0 = 0, x1 = 1;
    if (m == 1) return 1;
    while (a > 1) {
        q = a / m;
        t = m, m = a % m, a = t;
        t = x0, x0 = x1 - q * x0, x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}


int64_t bfun(int64_t k,int64_t N, int64_t P){
    return ((N+1-k) * mul_inv(k,P)) % P;
}

struct pack{
    int64_t Sr;
    int64_t ar;
    int64_t br;
};
void alg2(uint64_t N,uint64_t K,uint64_t P){

    uint64_t  S = modpower<uint64_t >(2,K,P);
    uint64_t   b=1;

    for (int i=K+1; i<=N; i++ ){
        S=(P+2*S-b)%P;
        b= (((b * i)%P) * mul_inv((P+i-K)%P,P)%P)%P;
    }

    cout<<S%P<<endl;

}



int main() {

    int64_t N,K,P;
    K = GetK();
    P = GetP();
    int nodes = NumberOfNodes();

    int  id = MyNodeId();


    if ( K<1000000 ){
        if (id==0){
            N = GetN();
            alg2(N,K,P);
        }
        return 0;
    }


    if (MyNodeId()==0){ //N, b,b
        N = GetN();
        PutInt(1, N);
        PutInt(1, modpower<uint64_t >(2,K,P) );
        PutInt(1, 1);
        Send(1);
    }else {

        int64_t start_k = K + (P - 1 -K) * (id - 1) / (nodes - 1);
        int64_t end_k = K + (P - 1 -K) * (id) / (nodes - 1);

        int64_t Sr = 1;
        int64_t ar = 0;
        int64_t br = 1;

        vector< pack> bufor;

        bufor.reserve( end_k -start_k + 1);

        for (int i = start_k + 1; i <= end_k; i++) {
            Sr = (Sr * 2) % P;
            ar = (P+2 * ar - br) % P;
            br = (((br * i) % P) * mul_inv( (P+i - K)%P, P)) % P;
            bufor.push_back(pack{Sr, ar, br});

        }

        Receive(id - 1);
        N = GetInt(id - 1);
        uint64_t S = GetInt(id - 1);
        uint64_t b = GetInt(id - 1);

        if (N <= start_k) {//propagacje

        } else if (N > end_k) {
            S = (Sr * S + b * ar)%P;
            b = (b * br)%P;
        } else {//ze środka
            auto pak = bufor[ N - start_k -1 ];
            Sr=pak.Sr;
            ar=pak.ar;
            br=pak.br;
            S = (Sr * S + b * ar)%P;
            b = (b * br)%P;
        }
        PutInt((id + 1) % nodes, N);
        PutInt((id + 1) % nodes, S);
        PutInt((id + 1) % nodes, b);
        Send((id + 1) % nodes);
    }

    if (MyNodeId()==0) {
        Receive(nodes - 1);
        N = GetInt(nodes - 1);
        uint64_t S = GetInt(nodes - 1);
        uint64_t b = GetInt(nodes - 1);

        cout << S  << endl;
    }



}