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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include "poszukiwania.h"
#include "message.h"

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cassert>
using namespace std;



const unsigned int MOD = 1000696969;
const unsigned int POD = 2137;
const unsigned int INV = 430810113;

unsigned long long int podniesDoPotegiModulo(unsigned long long int podstawa, unsigned long long int wykladnik) {
    if (wykladnik == 0) return 1;
    unsigned long long int wynik = 1;
    unsigned long long int podstawaMod = podstawa % MOD;
    for (long long int i = 1; i <= wykladnik; i <<= 1) {
        podstawaMod %= MOD;
        if (wykladnik & i) {
            wynik *= podstawaMod;
            wynik %= MOD;
        }
        podstawaMod *= podstawaMod;
    }
    return wynik;
}


int main() { 
const long long N = SignalLength();
const long long M = SeqLength();
const int id = MyNodeId();
const int nodes = NumberOfNodes();
/*	const long long dN = (N + nodes - 1) / nodes;
  	const long long sN = dN * id;
	const long long kN = min(sN + dN, N);
	unsigned int part_hashN = 0;
	unsigned int podPot = 1;
	for (long long i = sN; i < kN; i++) {
		part_hashN = ((unsigned long long) part_hashN + ((unsigned long long) SignalAt(i + 1) * (unsigned long long) podPot) % MOD) % MOD;
		podPot = ((unsigned long long) podPot * (unsigned long long) POD) % MOD;
	}
	PutInt(0, part_hashN);
	Send(0);*/
	/*if (id == 0) {
		unsigned int hashN = 0;
		for (int i = 0; i < nodes; i++) {
			Receive(i);
			unsigned int recv = GetInt(i);
			hashN = ((unsigned long long) hashN + ((unsigned long long) recv * podniesDoPotegiModulo(POD, dN * i)) % MOD) % MOD;
		}
		unsigned int* hasze1 = new unsigned int[M];
		unsigned int hasze1_sum = 0; // pamietac o przypadku ze p == 0!!!
		podPot = 1;
		for (long long i = 0; i < M; i++) {
			hasze1_sum = ((unsigned long long) hasze1_sum + ((unsigned long long) SeqAt(i + 1) * (unsigned long long) podPot) % MOD) % MOD;
			hasze1[i] = hasze1_sum;
			podPot = ((unsigned long long) podPot * (unsigned long long) POD) % MOD;
		}
		podPot = 1;
		long long res = 0;
		for (long long i = 0; i <= M - N; i++) {
			unsigned long long tmp = (hasze1[i + N - 1] + MOD - (i - 1 >= 0 ? hasze1[i - 1] : 0)) % MOD;
			//cout << tmp << " " << hashN << endl;
			if (tmp == ((unsigned long long)hashN * (unsigned long long)podPot) % MOD) res++;
			podPot = ((unsigned long long) podPot * (unsigned long long) POD) % MOD;
		}
		printf("%lld\n", res);
	}*/
	/*
	const long long dM = (M + nodes - 1) / nodes;
	const long long sM = dM * id;
	const long long kM = min(sM + dM, M);

	unsigned int* hasze1 = new unsigned int[dM];
	unsigned int hasze1_sum = 0; // pamietac o przypadku ze p == 0!!!
	podPot = 1;
	for (long long i = sM; i < kM; i++) {
		hasze1_sum = ((unsigned long long) hasze1_sum + ((unsigned long long) SeqAt(i + 1) * (unsigned long long) podPot) % MOD) % MOD;
		hasze1[i - sM] = hasze1_sum;
    	podPot = ((unsigned long long) podPot * (unsigned long long) POD) % MOD;
	}
	PutInt(0, hasze1_sum);
	Send(0);
	if (id == 0) {
		unsigned int hasze_range[nodes];
		for (int i = 0; i < nodes; i++) {
			Receive(i);
			hasze_range[i] = GetInt(i);
		}
		for (int i = 0; i < nodes; i++) {
			for (int j = 0; j < nodes; j++) {
				PutInt(i, hasze_range[j]);
			}
			Send(i);
		}
    }

	unsigned int hasze_range[nodes];
	Receive(0);
	for (int i = 0; i < nodes; i++) hasze_range[i] = GetInt(0);
	
	const long long sM2 = sM + N + 1;
	const long long kM2 = min(kM2 + N + 1, M);
	if (sM2 < M) {
		// mozna porownywac
		unsigned int* hasze2 = new unsigned int[dM];
		unsigned int hasze2_sum = 0; // pamietac o przypadku ze p == 0!!!
		podPot = 1;
		for (long long i = sM; i < kM; i++) {
			hasze2_sum = ((unsigned long long) hasze2_sum + ((unsigned long long) SeqAt(i + 1) * (unsigned long long) podPot) % MOD) % MOD;
			hasze2[i - sM] = hasze2_sum;
			podPot = ((unsigned long long) podPot * (unsigned long long) POD) % MOD;
		}
		long long x1 = sM, x2 = kM - 1;
		long long y1 = sM2, y2 = kM2 - 1;
		unsigned long long between = 0;
		long long pos = 0;
		for (int i = 0; i < nodes; i++) {
			long long z1 = dM * i, z2 = min(dM * i + dM, M) - 1;
			if (z1 <= x2 && z2 <= x2) {
				// nic
//cout << "TU1???" << endl;
			} else if (z1 >= y1 && z2 >= y1) {
				// nic
//cout << "TU2?2??" << endl;
			} else if (z1 >= x1 && z1 <= x2 && z2 > x2 && z2 < y1) {
				unsigned long long tmp = hasze_range[i];
				unsigned long long tmp2 = (unsigned long long) hasze1[x2 - x1] + (unsigned long long) MOD - (unsigned long long)(z1 - x1 - 1 >= 0 ? hasze1[z1 - x1 - 1] : 0);
				tmp -= (tmp2 * podniesDoPotegiModulo(INV, z1 - x1)) % MOD;
				tmp += MOD;
				tmp %= MOD;
				between += (tmp * podniesDoPotegiModulo(INV, x2 - z1) * podniesDoPotegiModulo(POD, pos)) % MOD;
				pos += z2 - x2;
				between %= MOD;
				//cout << "TU???" << endl;
			} else if (z2 >= y1 && z2 <= y2 && z1 > x2 && z1 < y1) {
				unsigned long long tmp = hasze_range[i];
				tmp -= (hasze2[z2 - y1] * podniesDoPotegiModulo(POD, y1 - z1)) % MOD;
				tmp += MOD;
				tmp %= MOD;
				between += (tmp * podniesDoPotegiModulo(POD, pos)) % MOD;
				pos += y1 - z1;
				between %= MOD;
//cout << "TU???" << endl;
			} else if (z1 >= x1 && z1 <= x2 && z2 >= y1 && z2 <= y2) {
				unsigned long long tmp = hasze_range[i];
				unsigned long long tmp2 = (unsigned long long) hasze1[x2 - x1] + (unsigned long long) MOD - (unsigned long long)(z1 - x1 - 1 >= 0 ? hasze1[z1 - x1 - 1] : 0);
				tmp -= (tmp2 * podniesDoPotegiModulo(INV, z1 - x1)) % MOD;
				tmp += MOD;
				tmp %= MOD;
				tmp -= (hasze2[z2 - y1] * podniesDoPotegiModulo(POD, y1 - z1)) % MOD;
				tmp += MOD;
				tmp %= MOD;
				between += (tmp * podniesDoPotegiModulo(INV, x2 - z1) * podniesDoPotegiModulo(POD, pos)) % MOD;
				pos += z2 - x2;
				between %= MOD;
//cout << "TU???" << endl;
			} else if (z1 > x2 && x1 < y1) {
				unsigned long long tmp = hasze_range[i];
				between += (tmp* podniesDoPotegiModulo(POD, pos)) % MOD;
				pos += z2 - z1;
				between %= MOD;
			} else {
				//cout << "ROZUM I GODNOSC CZLOWIEKA" << endl;
			}
		}
		//cout << between << endl;
		long long wyn = 0;
		for (long long i = sN; i < kN; i++) {
			unsigned long long tmp = (hasze1[kN - sN] + MOD - (i - sN - 1 >= 0 ? hasze1[i - sN - 1] : 0)) % MOD;
			tmp += between *  podniesDoPotegiModulo(POD, kN - i);
			tmp %= M;
			tmp += hasze2[i + N - sN2] *  podniesDoPotegiModulo(POD, kN - i + pos);
			tmp %= M;
			if (tmp == hashN)  wyn++;
		}
		cout << wyn << endl;
    } else {
		
    }*/
 	return 0;
}