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
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
using namespace std;
#include "poszukiwania.h"
#include "message.h"
long long liczenie( int pocz, int kon ){
    int x=31;
    long long j=1, potega=1, y=1000000007, wynik=0, hashw=0, hashwpop=0, hash[1000005], wzor=SignalLength();
    hash[0]=0;
    for( int i=1; i<=wzor; i++ ){
        potega=(potega*31)%y;
    }
    for( int i=1; i<=SignalLength(); i++ ){
        hashw=(hashwpop*x+SignalAt(i))%y;
        hashwpop=hashw;
    }
//    printf("%lld %lld", pocz, kon);
    for( int i=pocz; i<=kon; i++ ){
        hash[j]=(hash[j-1]*x+SeqAt(i))%y;
        if( i-wzor+1>=pocz ){
            if( (hash[j]-(hash[j-wzor]*potega)%y)%y==hashw )
                wynik++;
        }
        j++;
    }
    for( int i=1; i<=1000001; i++ ){
        hash[i]=0;
    }
    return wynik;
}
int main(){
    if( SignalLength()>1000000 ){
        if( MyNodeId()==0 ){
            printf("0\n");
        }
        return 0;
    }
    int wzor=SignalLength();
    int ciag=SeqLength();
    int N=NumberOfNodes();
    int node=MyNodeId();
    int p=0;
    int k=0;
    long long odp=0;
    if( node>0 ){
        if( ciag/(N/2)>=wzor ){
            int dlugosc=ciag/(N/2);
            int dlugosc_ost=ciag-(((N/2)-1)*dlugosc);
            if( node>=1 && node<N/2 ){
                p=(node-1)*dlugosc+1;
                k=p+dlugosc-1;
            }
            if( node==N/2 ){
                p=((N/2)-1)*dlugosc+1;
                k=ciag;
            }
            if( node>N/2 && node<=2*(N/2)-1 ){
                p=(node-(N/2))*dlugosc+2-wzor;
                k=(node-(N/2))*dlugosc+wzor-1;
            }
        }
        else{
            int dlugosc=wzor;
            int glowne=(ciag+(wzor-1))/wzor;
            int graniczne=glowne-1;
            if( node<glowne ){
                p=((node-1)*dlugosc)+1;
                k=p+dlugosc-1;
            }
            if( node==glowne ){
                p=((node-1)*dlugosc)+1;
                k=ciag;
            }
            if( node>glowne && node<=glowne+graniczne ){
                p=((node-glowne)*wzor)+2-wzor;
                k=min(ciag, (((node-glowne)*wzor)+wzor-1));
            }
        }
        if( p<k && k-p<=1000000 )
            odp=liczenie(p, k);
        PutLL(0, odp);
        Send(0);
    }
    if( node==0 ){
        long long sum=0;
        for( int i=1; i<N; i++ ){
            Receive(i);
            long long wartosc=GetLL(i);
            sum+=wartosc;
        }
        printf("%lld\n", sum);
    }
    return 0;
}