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

struct nwd_t{
    long long int xa,xb,nwd;
};

void _nwd(long long int a,long long int b,long long int xaOld,long long int xaOlder,nwd_t *nwd){
    if(b)
        _nwd(b,a%b,xaOlder-a/b*xaOld,xaOld,nwd);
    else{
        nwd->xa=xaOlder;
        nwd->nwd=a;
    }
}

void NWD(long long int a,long long int b,nwd_t *nwd){
    _nwd(a,b,0,1,nwd);
    nwd->xb=(nwd->nwd-a*nwd->xa)/b;
}

long long int norm(long long int a,long long int p){
    return ((a%p)+p)%p;
}

long long int rev(long long int a,long long int p){
    nwd_t n;
    NWD(a,p,&n);
    return norm(n.xa,p);
}

int main() {
    long long int n = GetN(), k = GetK(), p = GetP();
    long long int last=1,sum=0;
    long long int poczatek = (MyNodeId() * (k+1)) / NumberOfNodes();
    long long int koniec = ((MyNodeId() + 1) * (k+1)) / NumberOfNodes();
    for(int i=(poczatek>1?poczatek:1);i<koniec;i++){
        long long int licznik=norm(n-i+1,p);
        long long int mianownik=rev(i,p);
        last=norm(norm(last*licznik,p)*mianownik,p);
        sum=norm(sum+last,p);
    }
    int next=(MyNodeId()+1)%NumberOfNodes();
    int prev=(MyNodeId()-1+NumberOfNodes())%NumberOfNodes();
    if(MyNodeId() != 0){
        Receive(prev);
        long long int poprzedniaSuma=GetLL(prev);
        long long int poprzedniElement=GetLL(prev);
        last=norm(last*poprzedniElement,p);
        sum=norm(sum*poprzedniElement+poprzedniaSuma,p);
    }
    PutLL(next,sum);
    PutLL(next,last);
    Send(next);
    if(MyNodeId() == 0){
        Receive(prev);
        long long int poprzedniaSuma=GetLL(prev);
        printf("%lld\n",norm(poprzedniaSuma+1,p));
    }
}