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

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

long long int s, m, q1, q2, d, hs1, hs2, hm1, hm2, f1, f2, maxd, wynik, w, no_maxn, no_off;

long long int mod(long long int a, long long int b, long long int m)
{
	long long int i;
	long long int result = 1;
	long long int x = a%m;

	for (i = 1; i <= b; i <<= 1)
	{
		x %= m;
		if ((b&i) != 0)
		{
			result *= x;
			result %= m;
		}
		x *= x;
	}

	return result%m;
}

int main()
{
	d = 1000000007;
	q1 = 1000010153;
	q2 = 1003010219;
	s = SignalLength();
	m = SeqLength();
	long long int non = NumberOfNodes();
	long long int myn = MyNodeId();

	maxd = m - s;

	long long int prze = (maxd + 1) / non;
	long long int res = (maxd + 1) % non;
	long long int rmi = min(res, myn);

	no_off = myn * prze + rmi;
	if (prze > 0)
	{
		no_maxn = (myn + 1) * prze - 1 + rmi;

		if (myn < res)
		{
			no_maxn++;
		}
	}
	else
	{
		no_maxn = rmi;
		if (rmi == res)
		{
			no_maxn = 0;
		}
	}

	no_maxn = min(no_maxn, maxd);

	if (no_off <= no_maxn)
	{
		for (long long int i = 0; i < s; ++i)
		{
			long long int a = SignalAt(i + 1);
			long long int b = SeqAt(no_off + i + 1);
			hs1 = (hs1*d + a) % q1;
			hm1 = (hm1*d + b) % q1;
			hs2 = (hs2*d + a) % q2;
			hm2 = (hm2*d + b) % q2;
		}

		f1 = mod(d, s - 1, q1);
		f2 = mod(d, s - 1, q2);


		for (long long int i = no_off; i <= no_maxn; ++i)
		{
			if (hs1 == hm1)
			{
				if (hs2 == hm2)
				{
					wynik++;
				}
			}
			if (i < no_maxn)
			{
				long long int a = SeqAt(i + 1);
				long long int b = SeqAt(s + i + 1);
				hm1 = (d*(hm1 - a * f1) + b) % q1;
				hm2 = (d*(hm2 - a * f2) + b) % q2;
				if (hm1 < 0) hm1 += q1;
				if (hm2 < 0) hm2 += q2;
			}
		}

	}

	PutLL(0, wynik);
	Send(0);

	if (MyNodeId() == 0)
	{
		for (int i = 0; i < non; ++i)
		{
			int from = Receive(-1);
			w += GetLL(from);
		}

		printf("%llu", w);
	}

	return 0;
}