#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #include "message.h" #include "poszukiwania.h" #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back #define base 1000000087 #define mod 1000696969 #define debug 1 using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; ll pot(ll a,ll b){ll w=1;while(b){if(b&1)w=w*a%mod;a=a*a%mod;b>>=1;}return w;} pii przwz[120],prztxt[120]; int inst,instn,instm,id,n,m,dwz[120],dtxt[120],__HASZ__[20300005],*hasz; bool check(int a) { REP(i,10) { int x=rand()%m; if (SeqAt(a+x)!=SignalAt(1+x)) return false; } return true; } int main() { inst=NumberOfNodes()-1; instn=inst; instm=inst; id=MyNodeId(); n=SeqLength(); m=SignalLength(); if (inst<=m) { fill(dwz+1,dwz+inst+1,m/inst); FOR(i,inst-m%inst+1,inst) dwz[i]++; przwz[1]=mp(1,dwz[1]); FOR(i,2,inst) przwz[i]=mp(przwz[i-1].e2+1,przwz[i-1].e2+dwz[i]); } else FOR(i,1,m) przwz[i]=mp(i,i),instm=m,dwz[i]=1; if (inst<=n) { fill(dtxt+1,dtxt+inst+1,n/inst); FOR(i,inst-n%inst+1,inst) dtxt[i]++; prztxt[1]=mp(1,dtxt[1]); FOR(i,2,inst) prztxt[i]=mp(prztxt[i-1].e2+1,prztxt[i-1].e2+dtxt[i]); } else FOR(i,1,n) prztxt[i]=mp(i,i),instn=n,dtxt[i]=1; if (id==0) { Receive(instm); int haszwzorca=GetInt(instm); FOR(i,1,instn) PutInt(i,haszwzorca),Send(i); int wyn=0; FOR(i,1,instn) Receive(i),wyn+=GetInt(i); printf("%d",wyn); } else { if (id<=instm) { ll p=pot(base,przwz[id].e1),hash=0; FOR(i,przwz[id].e1,przwz[id].e2) hash=(hash+p*SignalAt(i))%mod,p=p*base%mod; if (id>1) { Receive(id-1); int dod=GetInt(id-1); hash=(hash+dod)%mod; } if (id==instm) PutInt(0,(int)hash),Send(0); else PutInt(id+1,hash),Send(id+1); } if (id<=instn) { Receive(0); ll haszwzorca=GetInt(0); hasz=__HASZ__-prztxt[id].e1+1; ll p=pot(base,prztxt[id].e1); FOR(i,prztxt[id].e1,prztxt[id].e2) hasz[i]=(hasz[i-1]+p*SeqAt(i))%mod,p=p*base%mod; int dod=0,wyslij=hasz[prztxt[id].e2]; if (id>1) { Receive(id-1); dod=GetInt(id-1); wyslij=(hasz[prztxt[id].e2]+dod)%mod; } if (id<instn) PutInt(id+1,wyslij),Send(id+1); FOR(i,prztxt[id].e1-1,prztxt[id].e2) hasz[i]=(hasz[i]+dod)%mod; FOR(i,1,instn) { int miejsce=prztxt[i].e1+m-1; if (miejsce<prztxt[id].e1 || miejsce>prztxt[id].e2) continue; PutInt(i,hasz[miejsce]); Send(i); } int miejsce=prztxt[id].e1+m-1,ret=0; if (miejsce<=n) { FOR(i,1,instn) { if (miejsce<prztxt[i].e1 || miejsce>prztxt[i].e2) continue; Receive(i); dod=GetInt(i); } ll hash=dod; p=pot(base,miejsce); haszwzorca=haszwzorca*pot(base,miejsce-m)%mod; FOR(i,miejsce,miejsce+dtxt[id]-1) { if ((hash-hasz[i-m]+mod)%mod==haszwzorca && check(i-m+1)) ret++; if (i>=n) break; haszwzorca=haszwzorca*base%mod; p=p*base%mod; hash=(hash+p*SeqAt(i+1))%mod; } } PutInt(0,ret); Send(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 139 | #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #include "message.h" #include "poszukiwania.h" #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back #define base 1000000087 #define mod 1000696969 #define debug 1 using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; ll pot(ll a,ll b){ll w=1;while(b){if(b&1)w=w*a%mod;a=a*a%mod;b>>=1;}return w;} pii przwz[120],prztxt[120]; int inst,instn,instm,id,n,m,dwz[120],dtxt[120],__HASZ__[20300005],*hasz; bool check(int a) { REP(i,10) { int x=rand()%m; if (SeqAt(a+x)!=SignalAt(1+x)) return false; } return true; } int main() { inst=NumberOfNodes()-1; instn=inst; instm=inst; id=MyNodeId(); n=SeqLength(); m=SignalLength(); if (inst<=m) { fill(dwz+1,dwz+inst+1,m/inst); FOR(i,inst-m%inst+1,inst) dwz[i]++; przwz[1]=mp(1,dwz[1]); FOR(i,2,inst) przwz[i]=mp(przwz[i-1].e2+1,przwz[i-1].e2+dwz[i]); } else FOR(i,1,m) przwz[i]=mp(i,i),instm=m,dwz[i]=1; if (inst<=n) { fill(dtxt+1,dtxt+inst+1,n/inst); FOR(i,inst-n%inst+1,inst) dtxt[i]++; prztxt[1]=mp(1,dtxt[1]); FOR(i,2,inst) prztxt[i]=mp(prztxt[i-1].e2+1,prztxt[i-1].e2+dtxt[i]); } else FOR(i,1,n) prztxt[i]=mp(i,i),instn=n,dtxt[i]=1; if (id==0) { Receive(instm); int haszwzorca=GetInt(instm); FOR(i,1,instn) PutInt(i,haszwzorca),Send(i); int wyn=0; FOR(i,1,instn) Receive(i),wyn+=GetInt(i); printf("%d",wyn); } else { if (id<=instm) { ll p=pot(base,przwz[id].e1),hash=0; FOR(i,przwz[id].e1,przwz[id].e2) hash=(hash+p*SignalAt(i))%mod,p=p*base%mod; if (id>1) { Receive(id-1); int dod=GetInt(id-1); hash=(hash+dod)%mod; } if (id==instm) PutInt(0,(int)hash),Send(0); else PutInt(id+1,hash),Send(id+1); } if (id<=instn) { Receive(0); ll haszwzorca=GetInt(0); hasz=__HASZ__-prztxt[id].e1+1; ll p=pot(base,prztxt[id].e1); FOR(i,prztxt[id].e1,prztxt[id].e2) hasz[i]=(hasz[i-1]+p*SeqAt(i))%mod,p=p*base%mod; int dod=0,wyslij=hasz[prztxt[id].e2]; if (id>1) { Receive(id-1); dod=GetInt(id-1); wyslij=(hasz[prztxt[id].e2]+dod)%mod; } if (id<instn) PutInt(id+1,wyslij),Send(id+1); FOR(i,prztxt[id].e1-1,prztxt[id].e2) hasz[i]=(hasz[i]+dod)%mod; FOR(i,1,instn) { int miejsce=prztxt[i].e1+m-1; if (miejsce<prztxt[id].e1 || miejsce>prztxt[id].e2) continue; PutInt(i,hasz[miejsce]); Send(i); } int miejsce=prztxt[id].e1+m-1,ret=0; if (miejsce<=n) { FOR(i,1,instn) { if (miejsce<prztxt[i].e1 || miejsce>prztxt[i].e2) continue; Receive(i); dod=GetInt(i); } ll hash=dod; p=pot(base,miejsce); haszwzorca=haszwzorca*pot(base,miejsce-m)%mod; FOR(i,miejsce,miejsce+dtxt[id]-1) { if ((hash-hasz[i-m]+mod)%mod==haszwzorca && check(i-m+1)) ret++; if (i>=n) break; haszwzorca=haszwzorca*base%mod; p=p*base%mod; hash=(hash+p*SeqAt(i+1))%mod; } } PutInt(0,ret); Send(0); } } } |