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
#pragma region Template 
#include <bits/stdc++.h> 

using namespace std;

#define For(i, n) for (int i = 0; i < (n); i++)
#define ForD(i, n) for (int i = (n) - 1; i >= 0; i--)
#define SORT(x) sort(begin(x), end(x))
#define REP(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#if DEBUG
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string>) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << endl;
	err(++it, args...);
}
#else
#define error(...) do {} while (0)
#endif

#define _upgrade do { ios::sync_with_stdio(0); cin.tie(0); } while (0)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#pragma endregion 

#include "message.h"
#include "futbol.h"

inline int mulmod(int a,int b,int mo) {
	int d,r;
	if(a==0 || b==0) return 0;
	if(a==1 || b==1) return max(a,b);
	__asm__("mull %4;"
	        "divl %2"
		: "=d" (r), "=a" (d)
		: "r" (mo), "a" (a), "d" (b));
	return r;
}

int modpow(int a, int n, int mo) {
	int r=1;
	while(n) r=mulmod(r,(n%2)?a:1,mo),a=mulmod(a,a,mo),n>>=1;
	return r;
}

inline int modinv(int a, int mo) { return modpow(a, mo - 2, mo); }

int main() {
    int my_node_id = MyNodeId();
    int num_of_nodes = NumberOfNodes();

	int n = GetN();
    int k = GetK();
    int p = GetP();

    int per_node = max(1, k / num_of_nodes); 
	int my_first_pos = my_node_id * per_node;
	int my_last_len = my_node_id < (num_of_nodes - 1)
	                  ? per_node * (my_node_id + 1)
					  : k;

    int bn = 1;
    int sum = my_node_id == 0 ? 1 : 0;

    if (my_node_id < k) {
        for (int i = my_first_pos; i < my_last_len; i++) {
            int top = n - i; 
            if (top % (i + 1) == 0) {
                top /= (i + 1);
                bn = (int)(((ll)bn * (ll)top) % (ll)p);
            } else {
                int inv = modinv(i + 1, p);
                bn = (int)((((ll)bn * (ll)top) % (ll)p * (ll)inv) % (ll)p);
            }

            sum += bn;
            sum %= p;
        }
    }

    if (my_node_id != 0) {
        Receive(my_node_id - 1);
        int prev_bn = GetInt(my_node_id - 1);
        int prev_sum = GetInt(my_node_id - 1);

        sum = int((((ll)sum * (ll)prev_bn) + prev_sum) % (ll)p);
        bn = (int)(((ll)prev_bn * bn) % (ll)p);
    }

    if (my_node_id != num_of_nodes - 1) {
        PutInt(my_node_id + 1, bn);
        PutInt(my_node_id + 1, sum);
        Send(my_node_id + 1);
    } else {
        cout << sum << "\n";
    }
}