#include "message.h" #include "poszukiwania.h" #include <cstdio> #include <algorithm> #include <cmath> #define ULL long long #define FT first #define SD second #define MP make_pair #define PLL pair<ULL, ULL> const ULL M=781332547; const ULL P=1009; using namespace std; int mynode, inst; ULL sig, seq, hash_sig, ile; ULL pot(ULL a, ULL n)//szybkie potęgowanie a^n mod M { ULL w=1; while (n>0) { if (n%2==1) //jesli bit jest = 1 w=(w*a)%M; a=(a*a)%M; n/=2; //skrócenie o jeden bit } return w; } PLL podzial(ULL k)//zwraca PLL z przedziałem, na którym ma działać ta instancja; k - długość ciągu { PLL wyn; ULL r=k%(inst-1); if (mynode>0) { ULL tmp=k/(inst-1); wyn.FT=(mynode-1)*tmp+r+1; wyn.SD=wyn.FT+tmp; } else { wyn.FT=1; wyn.SD=r+1; } return wyn; } ULL hashuj_sig(PLL gdzie)//hashuje sygnał { ULL wyn=0; for (ULL i=gdzie.FT; i<gdzie.SD; ++i) { wyn=(wyn*P)%M; wyn=(wyn+SignalAt(i))%M; } return wyn; } ULL hashuj_seq(PLL gdzie) { ULL wyn=0; for (ULL i=gdzie.FT; i<gdzie.SD; ++i) { wyn=(wyn*P)%M; wyn=(wyn+SeqAt(i))%M; } return wyn; } int main() { mynode=MyNodeId(); srand(mynode); inst=NumberOfNodes(); sig=SignalLength(); seq=SeqLength(); PLL przedzial=podzial(sig); hash_sig=hashuj_sig(przedzial); if (mynode>0) { PutLL(0, hash_sig); Send(0); Receive(0); hash_sig=GetLL(0); } else { ULL dl=sig/(inst-1), mnoznik=pot(P, dl); for (int i=1; i<inst; ++i) { hash_sig=(hash_sig*mnoznik)%M; Receive(i); hash_sig=(hash_sig+GetLL(i))%M; } for (int i=1; i<inst; ++i) { PutLL(i, hash_sig); Send(i); } } przedzial=podzial(seq-sig+1);//dzielenie pozycji początkowych ULL hash_seq=hashuj_seq(MP(przedzial.FT, przedzial.FT+sig)); for (ULL i=przedzial.FT; i<przedzial.SD; ++i)//i-obecny potencjalny poczatek wzorca { if (hash_seq==hash_sig) { bool ok=true; for (int q=0; q<4; ++q) { ULL losowa=(rand())%sig+1; if (SignalAt(losowa)!=SeqAt(losowa+i-1)) ok=false; } if (ok) ile++; } hash_seq=(hash_seq*P)%M; hash_seq=(hash_seq+SeqAt(i+sig))%M; ULL tmp=(pot(P, sig)*SeqAt(i))%M; hash_seq=(hash_seq-tmp+M)%M; } if (mynode>0) { PutLL(0, ile); Send(0); } else { for (int i=1; i<inst; ++i) { Receive(i); ile+=GetLL(i); } printf("%llu\n", ile); } return 0; }
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 | #include "message.h" #include "poszukiwania.h" #include <cstdio> #include <algorithm> #include <cmath> #define ULL long long #define FT first #define SD second #define MP make_pair #define PLL pair<ULL, ULL> const ULL M=781332547; const ULL P=1009; using namespace std; int mynode, inst; ULL sig, seq, hash_sig, ile; ULL pot(ULL a, ULL n)//szybkie potęgowanie a^n mod M { ULL w=1; while (n>0) { if (n%2==1) //jesli bit jest = 1 w=(w*a)%M; a=(a*a)%M; n/=2; //skrócenie o jeden bit } return w; } PLL podzial(ULL k)//zwraca PLL z przedziałem, na którym ma działać ta instancja; k - długość ciągu { PLL wyn; ULL r=k%(inst-1); if (mynode>0) { ULL tmp=k/(inst-1); wyn.FT=(mynode-1)*tmp+r+1; wyn.SD=wyn.FT+tmp; } else { wyn.FT=1; wyn.SD=r+1; } return wyn; } ULL hashuj_sig(PLL gdzie)//hashuje sygnał { ULL wyn=0; for (ULL i=gdzie.FT; i<gdzie.SD; ++i) { wyn=(wyn*P)%M; wyn=(wyn+SignalAt(i))%M; } return wyn; } ULL hashuj_seq(PLL gdzie) { ULL wyn=0; for (ULL i=gdzie.FT; i<gdzie.SD; ++i) { wyn=(wyn*P)%M; wyn=(wyn+SeqAt(i))%M; } return wyn; } int main() { mynode=MyNodeId(); srand(mynode); inst=NumberOfNodes(); sig=SignalLength(); seq=SeqLength(); PLL przedzial=podzial(sig); hash_sig=hashuj_sig(przedzial); if (mynode>0) { PutLL(0, hash_sig); Send(0); Receive(0); hash_sig=GetLL(0); } else { ULL dl=sig/(inst-1), mnoznik=pot(P, dl); for (int i=1; i<inst; ++i) { hash_sig=(hash_sig*mnoznik)%M; Receive(i); hash_sig=(hash_sig+GetLL(i))%M; } for (int i=1; i<inst; ++i) { PutLL(i, hash_sig); Send(i); } } przedzial=podzial(seq-sig+1);//dzielenie pozycji początkowych ULL hash_seq=hashuj_seq(MP(przedzial.FT, przedzial.FT+sig)); for (ULL i=przedzial.FT; i<przedzial.SD; ++i)//i-obecny potencjalny poczatek wzorca { if (hash_seq==hash_sig) { bool ok=true; for (int q=0; q<4; ++q) { ULL losowa=(rand())%sig+1; if (SignalAt(losowa)!=SeqAt(losowa+i-1)) ok=false; } if (ok) ile++; } hash_seq=(hash_seq*P)%M; hash_seq=(hash_seq+SeqAt(i+sig))%M; ULL tmp=(pot(P, sig)*SeqAt(i))%M; hash_seq=(hash_seq-tmp+M)%M; } if (mynode>0) { PutLL(0, ile); Send(0); } else { for (int i=1; i<inst; ++i) { Receive(i); ile+=GetLL(i); } printf("%llu\n", ile); } return 0; } |