#include "message.h" #include "poszukiwania.h" #include <bits/stdc++.h> using namespace std; const int md[3]={1000000103,1000000123,1000000181}; const long long H=1000000097; int le[111],ri[111],l[111],r[111],b[111][3],bp[111][3],c[3],p[3],h[3],z[3]; long long pwn[3]; long long pw(long long a, int b, int md) { if (b==0) return 1LL; if (b&1) return (pw(a,b-1,md)*a)%md; long long x=pw(a,b/2,md); return (x*x)%md; } int main() { int N=NumberOfNodes(); int M=MyNodeId(); int A=SignalLength(); int B=SeqLength(); int x=A/N,y=A%N; for (int i=0; i<N; i++) { le[i]=(i==0)?0:ri[i-1]; ri[i]=le[i]+x+int(i<y); } for (int j=0; j<3; j++) { p[j]=1; c[j]=0; } for (int i=le[M]; i<ri[M]; i++) { int cur=SignalAt(i+1); for (int j=0; j<3; j++) { p[j]=(p[j]*H)%md[j]; c[j]=(c[j]*H+cur)%md[j]; } } for (int i=0; i<N; i++) { for (int j=0; j<3; j++) { PutInt(i,p[j]); PutInt(i,c[j]); } Send(i); } for (int i=0; i<N; i++) { Receive(i); for (int j=0; j<3; j++) { int pp=GetInt(i); int cc=GetInt(i); h[j]=(1LL*h[j]*pp+cc)%md[j]; } } x=B/N; y=B%N; for (int i=0; i<N; i++) { l[i]=(i==0)?0:r[i-1]; r[i]=l[i]+x+int(i<y); } for (int j=0; j<3; j++) { p[j]=1; c[j]=0; } for (int i=l[M]; i<r[M]; i++) { int cur=SeqAt(i+1); for (int j=0; j<3; j++) { p[j]=(p[j]*H)%md[j]; c[j]=(c[j]*H+cur)%md[j]; } } for (int i=0; i<N; i++) { for (int j=0; j<3; j++) { PutInt(i,p[j]); PutInt(i,c[j]); } Send(i); } for (int i=0; i<N; i++) { Receive(i); for (int j=0; j<3; j++) { bp[i][j]=GetInt(i); b[i][j]=GetInt(i); } } int res=0; for (int j=0; j<3; j++) { int i; for (i=M; i<N; i++) if (r[i]<l[M]+A) z[j]=(1LL*z[j]*bp[i][j]+b[i][j])%md[j]; else break; if (i<N) for (int e=l[i]; e<l[M]+A-1; e++) z[j]=(z[j]*H+SeqAt(e+1))%md[j]; pwn[j]=pw(H,A-1,md[j]); } for (int i=l[M]; i<r[M] && i+A<=B; i++) { int cur=SeqAt(i+A); for (int j=0; j<3; j++) z[j]=(z[j]*H+cur)%md[j]; { int j=0; for (; j<3; j++) if (z[j]!=h[j]) break; if (j>=3) res++; } cur=SeqAt(i+1); for (int j=0; j<3; j++) z[j]=(z[j]+md[j]-(cur*pwn[j])%md[j])%md[j]; } PutInt(0,res); Send(0); if (M==0) { int sum=0; for (int i=0; i<N; i++) { Receive(i); sum+=GetInt(i); } cout<<sum<<'\n'; } 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 | #include "message.h" #include "poszukiwania.h" #include <bits/stdc++.h> using namespace std; const int md[3]={1000000103,1000000123,1000000181}; const long long H=1000000097; int le[111],ri[111],l[111],r[111],b[111][3],bp[111][3],c[3],p[3],h[3],z[3]; long long pwn[3]; long long pw(long long a, int b, int md) { if (b==0) return 1LL; if (b&1) return (pw(a,b-1,md)*a)%md; long long x=pw(a,b/2,md); return (x*x)%md; } int main() { int N=NumberOfNodes(); int M=MyNodeId(); int A=SignalLength(); int B=SeqLength(); int x=A/N,y=A%N; for (int i=0; i<N; i++) { le[i]=(i==0)?0:ri[i-1]; ri[i]=le[i]+x+int(i<y); } for (int j=0; j<3; j++) { p[j]=1; c[j]=0; } for (int i=le[M]; i<ri[M]; i++) { int cur=SignalAt(i+1); for (int j=0; j<3; j++) { p[j]=(p[j]*H)%md[j]; c[j]=(c[j]*H+cur)%md[j]; } } for (int i=0; i<N; i++) { for (int j=0; j<3; j++) { PutInt(i,p[j]); PutInt(i,c[j]); } Send(i); } for (int i=0; i<N; i++) { Receive(i); for (int j=0; j<3; j++) { int pp=GetInt(i); int cc=GetInt(i); h[j]=(1LL*h[j]*pp+cc)%md[j]; } } x=B/N; y=B%N; for (int i=0; i<N; i++) { l[i]=(i==0)?0:r[i-1]; r[i]=l[i]+x+int(i<y); } for (int j=0; j<3; j++) { p[j]=1; c[j]=0; } for (int i=l[M]; i<r[M]; i++) { int cur=SeqAt(i+1); for (int j=0; j<3; j++) { p[j]=(p[j]*H)%md[j]; c[j]=(c[j]*H+cur)%md[j]; } } for (int i=0; i<N; i++) { for (int j=0; j<3; j++) { PutInt(i,p[j]); PutInt(i,c[j]); } Send(i); } for (int i=0; i<N; i++) { Receive(i); for (int j=0; j<3; j++) { bp[i][j]=GetInt(i); b[i][j]=GetInt(i); } } int res=0; for (int j=0; j<3; j++) { int i; for (i=M; i<N; i++) if (r[i]<l[M]+A) z[j]=(1LL*z[j]*bp[i][j]+b[i][j])%md[j]; else break; if (i<N) for (int e=l[i]; e<l[M]+A-1; e++) z[j]=(z[j]*H+SeqAt(e+1))%md[j]; pwn[j]=pw(H,A-1,md[j]); } for (int i=l[M]; i<r[M] && i+A<=B; i++) { int cur=SeqAt(i+A); for (int j=0; j<3; j++) z[j]=(z[j]*H+cur)%md[j]; { int j=0; for (; j<3; j++) if (z[j]!=h[j]) break; if (j>=3) res++; } cur=SeqAt(i+1); for (int j=0; j<3; j++) z[j]=(z[j]+md[j]-(cur*pwn[j])%md[j])%md[j]; } PutInt(0,res); Send(0); if (M==0) { int sum=0; for (int i=0; i<N; i++) { Receive(i); sum+=GetInt(i); } cout<<sum<<'\n'; } return 0; } |